An algorithmic view on multi-related-segments: A unifying model for approximate common interval - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

An algorithmic view on multi-related-segments: A unifying model for approximate common interval

Résumé

A set of genes that are proximately located on multiple chromosomes often implies their origin from the same ancestral genomic segment or their involvement in the same biological process. Among the numerous studies devoted to model and infer these gene sets, the recently introduced approximate common interval (ACI) models capture gene loss events in addition to the gene insertion, duplication and inversion events already incorporated by earlier models. However, the computational tractability of the corresponding problems remains open in most of the cases. In this contribution, we propose a unifying model for ACI, namely Multi-related-segments (Mrs), and demonstrate that capturing gene losses induces intractability in many cases (answering an open question raised in [19,20]).
Fichier principal
Vignette du fichier
hal.pdf (362.63 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00630150 , version 1 (07-10-2011)
hal-00630150 , version 2 (15-03-2012)

Identifiants

Citer

Xiao Yang, Florian Sikora, Guillaume Blin, Sylvie Hamel, Roméo Rizzi, et al.. An algorithmic view on multi-related-segments: A unifying model for approximate common interval. 9th annual conference on Theory and Applications of Models of Computation (TAMC), May 2012, Beijing, China. pp.319-329, ⟨10.1007/978-3-642-29952-0_33⟩. ⟨hal-00630150v2⟩
348 Consultations
578 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More