“Quartet distance”的意思、由来-开放百科全书

The quartet distance^[1] is a way of measuring the distance between two phylogenetic trees. It is defined as the number of subsets of four leaves that are not related by the same topology in both trees.

Computing the quartet distance

The most straightforward computation of the quartet distance would require

time, where

is the number of leaves in the trees.

Gerth Stølting Brodal et al. found an algorithm that takes

time to compute the quartet distance between two multifurcating trees when

is the maximum degree of the trees,^[5] which is accessible in C, perl, and the R package [https://CRAN.R-project.org/package=Quartet Quartet].

References

1. ^{{cite journal|last1=Estabrook|first1=George F.|last2=McMorris|first2=F. R.|last3=Meacham|first3=Christopher A.|title=Comparison of Undirected Phylogenetic Trees Based on Subtrees of Four Evolutionary Units|journal=Systematic Zoology|date=1985|volume=34|issue=2|pages=193–200|jstor=2413326|doi=10.2307/2413326}}
2. ^{{citejournal|last=Bryant|first=D.|author2=J. Tsang|author3=P. E. Kearney|author4=M. Li.|title=Computing the quartet distance between evolutionary trees|journal=Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms|pages=285–286|publisher=ACM Press|location=N.Y.|date=11 Jan 2000|url=http://monod.uwaterloo.ca/papers/00Distance.ps}}
3. ^{{citebook|last=Brodal|first=Gerth Stølting|authorlink=Gerth Stølting Brodal|author2=Rolf Fagerberg|author3=Christian N.S. Pedersen|chapter=Computing the Quartet Distance Between Evolutionary Trees in Time

|title=Algorithmica|year=2001|pages=731–742|publisher=Springer-Verlag}}
4. ^{{citejournal|last=Brodal|first=Gerth Stølting|authorlink=Gerth Stølting Brodal|author2=Rolf Fagerberg |author3=Christian Nørgaard Storm Pedersen|journal=Algorithmica, Special issue on ISAAC 2001|issue=2|pages=377–395|title=Computing the Quartet Distance Between Evolutionary Trees in Time

|volume=38|year=2003 |doi=10.1007/s00453-003-1065-y}}
5. ^{{citejournal|last=Brodal|first=Gerth Stølting|authorlink=Gerth Stølting Brodal|author2=Rolf Fagerberg |author3=T Mailund |author4=Christian Nørgaard Storm Pedersen |author5=A Sand|journal=Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'13)|publisher=SIAM|year=2013|title=Efficient algorithms for computing the triplet and quartet distance between trees of arbitrary degree|pages=1814–1832|url=http://www.cs.au.dk/~gerth/papers/soda13.pdf}}