2MCB - McGill Centre for Bioinformatics (4th floor, Bellini Building, Life Sciences Complex ; 3649 Promenade Sir William Osler ; Montréal, Québec - Canada)
McGill University (845, rue Sherbrooke O. Montréal (Québec) Canada H3A 0G4 - Canada)
Abstract : A preliminary step to most comparative genomics studies is the annotation of chromosomes as ordered sequences of genes. Diff erent genetic mapping techniques often give rise to di fferent maps with unequal gene content and 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 . Our goal is to find a linearization of P that is as close as possible to O, in term of a given genomic distance. We first prove NP-completeness complexity results considering the breakpoint and the common interval distances. We then focus on the breakpoint distance and 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 and is empirically shown to produce solutions within 10% of the optimal solution, on simulated data. Applications to the analysis of grass genomes are presented.
https://hal-upec-upem.archives-ouvertes.fr/hal-00619755
Contributor : Guillaume Blin
<>
Submitted on : Saturday, October 22, 2011 - 4:33:59 PM
Last modification on : Friday, May 10, 2019 - 1:44:06 PM
Long-term archiving on: Monday, January 23, 2012 - 2:20:15 AM
Guillaume Blin, Eric Blais, Danny Hermelin, Pierre Guillon, Mathieu Blanchette, et al.. Gene Maps Linearization using Genomic Rearrangement Distances. Journal of Computational Biology, Mary Ann Liebert, 2007, 14 (4), pp.394-407. ⟨hal-00619755⟩
