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
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;
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
DOI :
10.1109/IJCBS.2009.42
