Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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]).
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00630150
Contributor : Guillaume Blin <>
Submitted on : Thursday, March 15, 2012 - 1:47:54 PM
Last modification on : Monday, July 20, 2020 - 12:34:51 PM
Long-term archiving on: : Monday, June 18, 2012 - 4:20:08 PM

File

hal.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

610

Files downloads

783