title: Computing the summed adjacency disruption number between two genomes with duplicate genes.
abstract: The increasing number of fully sequenced genomes has led to the study of genome rearrangements. Several approaches have been proposed to solve this problem, all of them being either too complex to be solved efficiently or too simple to be applied to genomes of complex organisms. The latest challenge has been to overcome the problem of having genomes with duplicate genes. This led to the definition of matching models and similarity measures. The idea is to find a matching between genes in two genomes, in order to disambiguate the data of duplicate genes and calculate a similarity measure. The problem becomes that of finding a matching that best preserves the order of genes in two genomes, where gene order is evaluated by a chosen similarity measure. This article presents new algorithms for computing the exact summed adjacency disruption number for two genomes with duplicate genes. Experimental results on a γ-Proteobacteria data set illustrate the approach.
authors.affiliation: Instituto Superior Técnico, Technical University of Lisbon and INESC-ID Lisboa, Rua Alves Redol 9, Lisbon, Portugal.
authors.forename: João
authors.initials: J
authors.lastname: Delgado
authors.forename: Inês
authors.initials: I
authors.lastname: Lynce
authors.forename: Vasco
authors.initials: V
authors.lastname: Manquinho
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods; D020563:Gammaproteobacteria / Q000235:genetics; D015321:Gene Rearrangement; D020131:Genes, Duplicate; D016678:Genome; D055641:Mathematical Concepts; D008957:Models, Genetic; D008969:Molecular Sequence Data