Inferring Gene Orders from Gene Maps using the Breakpoint Distance

Abstract : Preliminary to most comparative genomics studies is the annotation of chromosomes as ordered sequences of genes. Unfortunately, di fferent genetic mapping techniques usually give rise to di fferent maps with unequal gene content, and often containing sets of unordered neighboring genes. Only partial orders can thus be obtained from combining such maps. However, once a total order O is known for a given genome, it can be used as a reference to order genes of a closely related species characterized by a partial order P . In this paper, the problem is to fi nd a linearization of P that is as close as possible to O in term of the breakpoint distance. We first prove an NP-complete complexity result for this problem. We then give a dynamic programming algorithm whose running time is exponential for general partial orders, but polynomial when the partial order is derived from a bounded number of genetic maps. A time-effi cient greedy heuristic is then given for the general case, with a performance higher than 90% on simulated data. Applications to the analysis of grass genomes are presented.
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620364
Contributor : Guillaume Blin <>
Submitted on : Saturday, October 22, 2011 - 9:16:30 PM
Last modification on : Friday, May 10, 2019 - 1:44:06 PM
Long-term archiving on: Monday, January 23, 2012 - 2:20:26 AM

File

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620364, version 1

Collections

Citation

Guillaume Blin, Eric Blais, Pierre Guillon, Mathieu Blanchette, Nadia El-Mabrouk. Inferring Gene Orders from Gene Maps using the Breakpoint Distance. 4th Annual RECOMB Satellite Workshop on Comparative Genomics (RECOMB-CG'06), Sep 2006, Montréal, Canada. pp.99-112. ⟨hal-00620364⟩

Share

Metrics

Record views

981

Files downloads

869