DocumentCode
3455619
Title
A Quadratic Time Algorithm for Computing the Quartet Distance between Two General Trees
Author
Mailund, Thomas ; Nielsen, Jesper ; Pedersen, Christian N S
Author_Institution
Bioinf. Res. Centre, Aarhus Univ., Aarhus, Denmark
fYear
2009
fDate
3-5 Aug. 2009
Firstpage
565
Lastpage
568
Abstract
We derive a quadratic time and space algorithm for computing the quartet distance between a pair of general trees, i.e. trees where inner nodes can have any degreeges3. The time and space complexity of our algorithm is quadratic in the number of leaves and does not depend on the degree of the inner nodes. This makes it the fastest algorithm for computing the quartet distance between general trees independent of the degree of the inner nodes.
Keywords
biology; computational complexity; trees (mathematics); quadratic space-time algorithm; quartet distance; species; time-space complexity; trees; Binary trees; Bioinformatics; Biology computing; Costs; Evolution (biology); Intelligent systems; Steel; Systematics; Systems biology; Topology; Quartet distance; algorithm; evolutionary trees;
fLanguage
English
Publisher
ieee
Conference_Titel
Bioinformatics, Systems Biology and Intelligent Computing, 2009. IJCBS '09. International Joint Conference on
Conference_Location
Shanghai
Print_ISBN
978-0-7695-3739-9
Type
conf
DOI
10.1109/IJCBS.2009.42
Filename
5260460
Link To Document