Faster exact computation of rSPR distance

被引：10

作者：

Chen, Zhi-Zhong ^{[1
]}

Fan, Ying ^{[2
]}

Wang, Lusheng ^{[2
]}

机构：

[1] Tokyo Denki Univ, Div Informat Syst Design, Hiki, Saitama 3590394, Japan

[2] City Univ Hong Kong, Dept Comp Sci, Kowloon, Hong Kong, Peoples R China

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2015年 / 29卷 / 03期

关键词：

Phylogenetic tree; rSPR distance; Fixed-parameter algorithm; GENE-TRANSFER; APPROXIMATION; ALGORITHMS; COMPLEXITY; TOOL; FPT;

D O I：

10.1007/s10878-013-9695-8

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

Due to hybridization events in evolution, studying two different genes of a set of species may yield two related but different phylogenetic trees for the set of species. In this case, we want to measure the dissimilarity of the two trees. The rooted subtree prune and regraft (rSPR) distance of the two trees has been used for this purpose, and many algorithms and software tools have been developed for computing the rSPR distance of two given phylogenetic trees. The previously fastest exact algorithm for this problem runs in time, where and are the number of leaves and the rSPR distance of the input trees, respectively. In this paper, we present a faster exact algorithm which runs in time. Our experiments show that the new algorithm is significantly faster than the newest version (namely, v1.1.1) of the previously best software (namely, rSPR) for RSPR distance.

引用

页码：605 / 635

页数：31

共 19 条

[1]

Barker NP, 2001, ANN MO BOT GARD, V88, P373, DOI 10.2307/3298585

[2] Phylogenetic identification of lateral genetic transfer events [J].

Beiko, RG ;

Hamilton, N .

BMC EVOLUTIONARY BIOLOGY, 2006, 6 (1) :17P

[3] Approximating subtree distances between phylogenies [J].

Bonet, Maria Luisa ;

John, Katherine St. ;

Mahindru, Ruchi ;

Amenta, Nina .

JOURNAL OF COMPUTATIONAL BIOLOGY, 2006, 13 (08) :1419-1434

[4]

Bordewich M., 2005, Annals of Combinatorics, V8, P409, DOI [10.1007/s00026-004-0229-z, DOI 10.1007/S00026-004-0229-Z]

[5] A 3-approximation algorithm for the subtree distance between phylogenies [J].

Bordewich, Magnus ;

McCartin, Catherine ;

Semple, Charles .

JOURNAL OF DISCRETE ALGORITHMS, 2008, 6 (03) :458-471

[6] An Ultrafast Tool for Minimum Reticulate Networks [J].

Chen, Zhi-Zhong ;

Wang, Lusheng .

JOURNAL OF COMPUTATIONAL BIOLOGY, 2013, 20 (01) :38-41

[7] A fast tool for minimum hybridization networks [J].

Chen, Zhi-Zhong ;

Wang, Lusheng ;

Yamanaka, Satoshi .

BMC BIOINFORMATICS, 2012, 13

[8] On the complexity of constructing evolutionary trees [J].

Gasieniec, L ;

Jansson, J ;

Lingas, A ;

Östlin, A .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 1999, 3 (2-3) :183-197

[9] Calculating SPR distances between trees [J].

Goloboff, Pablo A. .

CLADISTICS, 2008, 24 (04) :591-597

[10] On the complexity of comparing evolutionary trees [J].

Hein, J ;

Jiang, T ;

Wang, LS ;

Zhang, KZ .

DISCRETE APPLIED MATHEMATICS, 1996, 71 (1-3) :153-169

← 1 2 →