Reconstructing an ancestral genome using minimum segments duplications and reversals

We consider a particular model of genomic rearrangements that takes paralogous and orthologous genes-into account. Given a particular model of evolution and an optimization criterion, the problem is to recover an ancestor of a modern genome modeled as an ordered sequence of signed genes. One direct application is to infer gene orders at the ancestral nodes of a phylogenetic tree. Implicit in the rearrangement literature is that each gene has exactly one copy in each genome. This hypothesis is clearly false for species containing several copies of highly paralogous genes, e.g. multigene families. One of the most important regional event by which gene duplication can occur has been referred to as duplication transposition. Our model of evolution takes such duplications into account. For a genome G with gene families of different sizes, the implicit hypothesis is that G has an ancestor containing exactly one copy of each gene, and that G has evolved from this ancestor through a series of duplication transpositions and sub string reversals. The question is: how can we reconstruct an ancestral genome giving rise to the minimal number of duplication transpositions and reversals? The key idea is to reduce the problem to a series of subproblems involving genomes containing at most two copies of each gene. For this simpler version, we provide tight bounds, and we describe an algorithm, based on Hatmenhalli and Pevzner graph and result, that is exact when certain conditions are verified. We then show how to use this algorithm to recover gene orders at the ancestral nodes of a phylogenetic tree. (C) 2002 Elsevier Science (USA). All rights reserved.