 |
HAL UPEC - UPEM Portal |  |
 |
Conference papers
Inferring Positional Homologs with Common Intervals of Sequences
Abstract : Inferring orthologous and paralogous genes is an important problem in whole genomes comparisons, both for functional or evolutionary studies. In this paper, we introduce a new approach for inferring candidate pairs of orthologous genes between genomes, also called positional homologs, based on the conservation of the genomic context. We consider genomes represented by their gene order -- i.e. sequences of signed integers -- and common intervals of these sequences as the anchors of the final gene matching. We show that the natural combinatorial problem of computing a maximal cover of the two genomes using the minimum number of common intervals is NP-complete and we give a simple heuristic for this problem. We illustrate the effectiveness of this first approach using common intervals of sequences on two datasets, respectively 8 $\gamma$-proteobacterial genomes and the human and mouse whole genomes.
https://hal-upec-upem.archives-ouvertes.fr/hal-00620367
Contributor : Guillaume Blin Connect in order to contact the contributor
Submitted on : Tuesday, October 4, 2011 - 2:42:22 PM
Last modification on : Saturday, January 15, 2022 - 3:57:17 AM
Long-term archiving on: : Thursday, January 5, 2012 - 2:20:26 AM
Contributor : Guillaume Blin Connect in order to contact the contributor
Submitted on : Tuesday, October 4, 2011 - 2:42:22 PM
Last modification on : Saturday, January 15, 2022 - 3:57:17 AM
Long-term archiving on: : Thursday, January 5, 2012 - 2:20:26 AM
File
Blin_Chateau_Chauve_Gingras_RC...
Files produced by the author(s)