Finding all sorting tandem duplication random loss operations

被引：14

作者：

Bernt, Matthias ^{[1
]}

Chen, Kuan-Yu ^{[2
]}

Chen, Ming-Chiang ^{[2
]}

Chu, An-Chiang ^{[2
]}

Merkle, Daniel ^{[3
]}

Wang, Hung-Lung ^{[2
]}

Chao, Kun-Mao ^{[2
]}

Middendorf, Martin ^{[1
]}

机构：

[1] Univ Leipzig, Dept Comp Sci, Leipzig, Germany

[2] Natl Taiwan Univ, Dept Comp Sci & Informat Engn, Taipei, Taiwan

[3] Univ Southern Denmark, Dept Math & Comp Sci, Odense, Denmark

来源：

JOURNAL OF DISCRETE ALGORITHMS | 2011年 / 9卷 / 01期

关键词：

Genome rearrangement; Tandem duplication random loss; TDRL; Permutation;

D O I：

10.1016/j.jda.2010.09.006

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A tandem duplication random loss (TDRL) operation duplicates a contiguous segment of genes, followed by the random 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. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：32 / 48

页数：17

共 24 条

[1]

Ajana Y, 2002, LECT NOTES COMPUT SC, V2452, P300

[2] SHUFFLING CARDS AND STOPPING-TIMES [J].

ALDOUS, D ;

DIACONIS, P .

AMERICAN MATHEMATICAL MONTHLY, 1986, 93 (05) :333-348

[3]

BAFNA V, 1995, PROCEEDINGS OF THE SIXTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P614

[4]

Bayer D., 1992, ANN APPL PROBAB, V2, P294, DOI [DOI 10.1214/AOAP/1177005705, 10.1214/aoap/1177005705]

[5]

Bernt M, 2010, THESIS

[6] Using median sets for inferring phylogenetic trees [J].

Bernt, Matthias ;

Merkle, Daniel ;

Middendorf, Martin .

BIOINFORMATICS, 2007, 23 (02) :E129-E135

[7]

Bernt M, 2009, LECT NOTES COMPUT SC, V5577, P301, DOI 10.1007/978-3-642-02441-2_27

[8]

Boore J.L., 2000, DUPLICATION RANDOM L, V1, P133, DOI 10.1007/978-94-011-4309-7_13

[9] A variant of the tandem duplication - random loss model of genome rearrangement [J].

Bouvel, Mathilde ;

Rossin, Dominique .

THEORETICAL COMPUTER SCIENCE, 2009, 410 (8-10) :847-858

[10] Exploring the solution space of sorting by reversals, with experiments and an application to evolution [J].

Braga, Marilia D. V. ;

Sagot, Marie-France ;

Scornavacca, Celine ;

Tannier, Eric .

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 2008, 5 (03) :348-356

← 1 2 3 →