On the tandem duplication-random loss model of genome rearrangement

Kamalika Chaudhuri, Kevin Chen, Radu Mihaescu, Satish Rao

Research output: Contribution to conferencePaperpeer-review

39 Scopus citations

Abstract

We initiate the algorithmic study of a new model of genome rearrangement, the tandem duplication-random loss model, in which a genome evolves via successive rounds of tandem duplication of a contiguous segment of genes, followed by the loss of one copy of each of the duplicated genes. This model is well-known in the evolutionary biology literature, where it has been used to explain many of the known rearrangements in vertebrate mitochondrial genomes. Based on the model, we formalize a notion of distance between two genomes and show how to compute it efficiently for two interesting regions of the parameter space. We then consider median problems (i.e. finding the point which minimizes the sum of distances to a given set of points under some distance function) in the context of maximum parsimony phylogenetic reconstruction for these two special cases. Surprisingly, one of them turns out to correspond to the well-known rank aggregation problem, while the other corresponds to the biologically interesting case of whole genome duplication and loss, and we give an O(log log n) additive approximation algorithm for the latter.

Original languageEnglish (US)
Pages564-570
Number of pages7
DOIs
StatePublished - 2006
EventSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States
Duration: Jan 22 2006Jan 24 2006

Other

OtherSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityMiami, FL
Period1/22/061/24/06

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'On the tandem duplication-random loss model of genome rearrangement'. Together they form a unique fingerprint.

Cite this