Faster exact computation of rSPR distance

Zhi-Zhong Chen (), Ying Fan () and Lusheng Wang ()
Additional contact information
Zhi-Zhong Chen: Tokyo Denki University
Ying Fan: City University of Hong Kong
Lusheng Wang: City University of Hong Kong

Journal of Combinatorial Optimization, 2015, vol. 29, issue 3, No 6, 605-635

Abstract: Abstract 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 $$O\left( 2.415^dn\right) $$ O 2 . 415 d n time, where $$n$$ n and $$d$$ d 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 $$O\left( 2.344^dn\right) $$ O 2 . 344 d n 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.

Keywords: Phylogenetic tree; rSPR distance; Fixed-parameter algorithm (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9695-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:29:y:2015:i:3:d:10.1007_s10878-013-9695-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9695-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().