Finding All sorting tandem duplication random loss operations

Matthias Bernt*, Ming Chiang Chen, Daniel Merkle, Hung Lung Wang, Kun Mao Chao, Martin Middendorf

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

A tandem duplication random loss (TDRL) operation duplicates a contiguous segment of genes, followed by the loss of one copy of each of the duplicated genes. Although the importance of this operation is founded by several recent biological studies, it has been investigated only rarely from a theoretical point of view. Of particular interest are sorting TDRLs which are TDRLs that, when applied to a permutation representing a genome, reduce the distance towards another given permutation. The identification of sorting genome rearrangement operations in general is a key ingredient of many algorithms for reconstructing the evolutionary history of a set of species. In this paper we present methods to compute all sorting TDRLs for two given gene orders. In addition, a closed formula for the number of sorting TDRLs is derived and further properties of sorting TDRLs are investigated. It is also shown that the theoretical findings are useful for identifying unique sorting TDRL scenarios for mitochondrial gene orders.

Original languageEnglish
Title of host publicationCombinatorial Pattern Matching - 20th Annual Symposium, CPM 2009, Proceedings
Pages301-313
Number of pages13
DOIs
Publication statusPublished - 2009
Externally publishedYes
Event20th Annual Symposium on Combinatorial Pattern Matching, CPM 2009 - Lille, France
Duration: 2009 Jun 222009 Jun 24

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5577 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th Annual Symposium on Combinatorial Pattern Matching, CPM 2009
Country/TerritoryFrance
CityLille
Period2009/06/222009/06/24

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Finding All sorting tandem duplication random loss operations'. Together they form a unique fingerprint.

Cite this