Skip to Main content Skip to Navigation
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.
Complete list of metadatas
Contributor : Guillaume Blin <>
Submitted on : Tuesday, October 4, 2011 - 2:42:22 PM
Last modification on : Thursday, May 14, 2020 - 9:12:02 AM
Long-term archiving on: : Thursday, January 5, 2012 - 2:20:26 AM


Files produced by the author(s)


  • HAL Id : hal-00620367, version 1



Guillaume Blin, Annie Chateau, Cedric Chauve, Yannick Gingras. Inferring Positional Homologs with Common Intervals of Sequences. 4th Annual RECOMB Satellite Workshop on Comparative Genomics (RECOMB-CG'06), Sep 2006, Montreal, Canada. pp.24-38. ⟨hal-00620367⟩



Record views


Files downloads