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

https://hal-upec-upem.archives-ouvertes.fr/hal-00620367
Contributor : Guillaume Blin <>
Submitted on : Tuesday, October 4, 2011 - 2:42:22 PM
Last modification on : Wednesday, April 17, 2019 - 3:28:05 PM
Long-term archiving on : Thursday, January 5, 2012 - 2:20:26 AM

File

Blin_Chateau_Chauve_Gingras_RC...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620367, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

433

Files downloads

537