Journal of Computational Biology · 2008 · 27 citations · 12 references
Life SciencesBioinformaticsBiologyComparative GenomicsGenomic Data AnalysisGenomicsGene DuplicationGenome DuplicationGenomic Similarity MetricsMatchingMaximum Matching Approximation
Comparing genomes of different species is a fundamental problem in comparative genomics. Recent research has resulted in the introduction of different measures between pairs of genomes: for example, reversal distance, number of breakpoints, and number of common or conserved intervals. However, classical methods used for computing such measures are seriously compromised when genomes have several copies of the same gene scattered across them. Most approaches to overcome this difficulty are based either on the exemplar model, which keeps exactly one copy in each genome of each duplicated gene, or on the maximum matching model, which keeps as many copies as possible of each duplicated gene. The goal is to find an exemplar matching, respectively a maximum matching, that optimizes the studied measure. Unfortunately, it turns out that, in presence of duplications, this problem for each above-mentioned measure is NP-hard. In this paper, we propose to compute the minimum number of breakpoints and the maximum number of adjacencies between two genomes in presence of duplications using two different approaches. The first one is an exact, generic 0-1 linear programming approach, while the second is a collection of three heuristics. Each of these approaches is applied on each problem and for each of the following models: exemplar, maximum matching and intermediate model, that we introduce here. All these programs are run on a well-known public benchmark dataset of gamma-Proteobacteria, and their performances are discussed.
12
Transforming cabbage into turnip
Sridhar Hannenhalli, Pavel A. Pevzner · Journal of the ACM · 1999 · 652 citations · Full text
Life Sciences, Biology, Genetics +13
Evolutionary Origins of Genomic Repertoires in Bacteria
Emmanuelle Lerat, Vincent Daubin, Howard Ochman et al. · PLoS Biology · 2005 · 345 citations · Full text
Genome rearrangement with gene families
David Sankoff · Bioinformatics · 1999 · 222 citations · Full text
Life Sciences, Biology, Genetics +12