TY - GEN
T1 - Finding All sorting tandem duplication random loss operations
AU - Bernt, Matthias
AU - Chen, Ming Chiang
AU - Merkle, Daniel
AU - Wang, Hung Lung
AU - Chao, Kun Mao
AU - Middendorf, Martin
N1 - Funding Information:
This work was funded within the DAAD/NSC Joint Research Collaboration programme by grant D/05/06868 from the German Academic Exchange Service (DAAD) and NSC grants 95-2221-E-002-126-MY3 and 97-2221-E-002-097-MY3 from the National Science Council, Taiwan . This work was supported by the German Research Foundation (DFG) through the project “Deep Metazoan Phylogeny” within SPP 1174 .
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=70350655784&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70350655784&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-02441-2_27
DO - 10.1007/978-3-642-02441-2_27
M3 - Conference contribution
AN - SCOPUS:70350655784
SN - 3642024408
SN - 9783642024405
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 301
EP - 313
BT - Combinatorial Pattern Matching - 20th Annual Symposium, CPM 2009, Proceedings
T2 - 20th Annual Symposium on Combinatorial Pattern Matching, CPM 2009
Y2 - 22 June 2009 through 24 June 2009
ER -