Inferring Positional Homologs with Common Intervals of Sequences

Guillaume Blin 1 Annie Chateau 2 Cedric Chauve 2, 3 Yannick Gingras 2
1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 LaCIM - Laboratoire de combinatoire et d'informatique mathématique [Montréal]
3 Department of Mathematics [Burnaby]
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.
Document type :
Conference papers
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

LIGM_ALGO | UNIV-MLV | LIGM | ENPC | PARISTECH | UPEC-UPEM

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

433

Files downloads

537

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD