On the Reconstruction of Ancient Doubled Circular Genomes Using Minimum Reversals

Nadia El-Mabrouk[1] (mabrouk@iro.umontreal.ca)
David Sankoff[2] (sankoff@ere.umontreal.ca)

[1] Département d'informatique et de recherche opérationelle, Université de Montréal
CP 6128 succursale Centre-Ville, Montréal,Québec H3C 3J7
[2] Centre de recherches mathématiques, Université de Montréal
CP 6128 succursale Centre-Ville, Montréal,Québec H3C 3J7

Abstract

We propose a model of the doubling of a bacterial genome followed by gene order rearrangement to explain present-day patterns of duplicated genes. On the hypothesis that inversion (reversal) is the predominant mechanism of rearrangement, we ask how to reconstruct the ancestral genome at the moment of genome duplication. We present a polynomial algorithm for finding such a genome that minimizes (within 2 reversals) the Hannenhalli-Pevzner formula for reversal distance from the modern genome. We illustrate by applying the algorithm to a set of duplicate genes in the Marchantia polymorpha mitochondrial genome.

[ Full-text PDF | Table of Contents ]