Quartettabstand

Die Quartettdistanz ^{[ 1 ]} ist eine Methode zur Messung des Abstands zwischen zwei phylogenetischen Bäumen . Sie ist definiert als die Anzahl der Teilmengen von vier Blättern, die in beiden Bäumen nicht durch dieselbe Topologie miteinander verwandt sind.

Berechnung der Quartettdistanz

Die einfachste Berechnung der Quartettdistanz würde Zeit erfordern, wobei die Anzahl der Blätter in den Bäumen ist. $O(N^{4})$ $N$

Für Binärbäume wurden bessere Algorithmen zur Berechnung der Distanz gefunden.

$O(N^{2})$ Zeit ^{[ 2 ]}
$O(N\log ^{2}N)$ Zeit ^{[ 3 ]}

Und

$O(N\log N)$ Zeit ^{[ 4 ]}

Gerth Stølting Brodal et al. fanden einen Algorithmus, der Zeit benötigt, um die Quartettdistanz zwischen zwei sich verzweigenden Bäumen zu berechnen, wenn der maximale Grad der Bäume ist, ^[⁵^] der in C, Perl und dem R -Paket Quartet zugänglich ist . Archiviert am 19.01.2019 bei der Wayback Machine . $O(DN\log N)$ $D$

Referenzen

^ Estabrook, George F.; McMorris, FR; Meacham, Christopher A. (1985). „Vergleich ungerichteter phylogenetischer Bäume basierend auf Teilbäumen von vier evolutionären Einheiten“. Systematic Zoology . 34 (2): 193–200 . doi : 10.2307/2413326 . JSTOR 2413326 .
Bryant , D.; J. Tsang; P. E. Kearney; M. Li. (11. Januar 2000). „Berechnung des Quartettabstands zwischen evolutionären Bäumen“ . Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms . New York : ACM Press: 285–286 . Archiviert vom Original am 6. Juli 2011. Abgerufen am 3. Juni 2009 .
^ Brodal, Gerth Stølting; Fagerberg, Rolf; Pedersen, Christian NS (2001). „Berechnung der Quartettdistanz zwischen evolutionären Bäumen in der Zeit “. Algorithms and Computation . Lecture Notes in Computer Science. Band 2223. S. 731–742 . doi : 10.1007/3-540-45678-3_62 . ISBN $O(n\log ^{2}n)$ 978-3-540-42985-2Die
^ Brodal, Gerth Stølting ; Rolf Fagerberg; Christian Nørgaard Storm Pedersen (2003). „Berechnung des Quartettabstands zwischen Evolutionsbäumen in der Zeit “. Algorithmen . 38 (2): 377–395 . doi : 10.1007/s00453-003-1065-y . S2CID 6911940 . $O(n\log n)$
^ Brodal, Gerth Stølting ; Rolf Fagerberg; T Mailund; Christian Nørgaard Storm Pedersen; A Sand (2013). „Effiziente Algorithmen zur Berechnung der Tripel- und Quartettdistanz zwischen Bäumen beliebigen Grades“ (PDF) . Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms . SIAM: 1814–1832 . doi : 10.1137/1.9781611973105.130 . ISBN 978-1-61197-251-1Die

[eastbrook1985-1] Estabrook, George F.; McMorris, FR; Meacham, Christopher A. (1985). „Vergleich ungerichteter phylogenetischer Bäume basierend auf Teilbäumen von vier evolutionären Einheiten“. Systematic Zoology . 34 (2): 193–200 . doi : 10.2307/2413326 . JSTOR 2413326 .

[2] Bryant , D.; J. Tsang; P. E. Kearney; M. Li. (11. Januar 2000). „Berechnung des Quartettabstands zwischen evolutionären Bäumen“ . Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms . New York : ACM Press: 285–286 . Archiviert vom Original am 6. Juli 2011. Abgerufen am 3. Juni 2009 .

[3] Brodal, Gerth Stølting; Fagerberg, Rolf; Pedersen, Christian NS (2001). „Berechnung der Quartettdistanz zwischen evolutionären Bäumen in der Zeit “. Algorithms and Computation . Lecture Notes in Computer Science. Band 2223. S. 731–742 . doi : 10.1007/3-540-45678-3_62 . ISBN $O(n\log ^{2}n)$ 978-3-540-42985-2Die

[4] Brodal, Gerth Stølting ; Rolf Fagerberg; Christian Nørgaard Storm Pedersen (2003). „Berechnung des Quartettabstands zwischen Evolutionsbäumen in der Zeit “. Algorithmen . 38 (2): 377–395 . doi : 10.1007/s00453-003-1065-y . S2CID 6911940 . $O(n\log n)$

[5] Brodal, Gerth Stølting ; Rolf Fagerberg; T Mailund; Christian Nørgaard Storm Pedersen; A Sand (2013). „Effiziente Algorithmen zur Berechnung der Tripel- und Quartettdistanz zwischen Bäumen beliebigen Grades“ (PDF) . Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms . SIAM: 1814–1832 . doi : 10.1137/1.9781611973105.130 . ISBN 978-1-61197-251-1Die

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[

Quartettabstand

Berechnung der Quartettdistanz

Referenzen

Kategorien

Verwandte Artikel