Dystans kwartetowy

Odległość kwartetowa to sposób pomiaru odległości między dwoma drzewami filogenetycznymi . Jest definiowana jako liczba podzbiorów czterech liści, które nie są powiązane tą samą topologią w obu drzewach.

Obliczanie odległości kwartetu

Najprostsze obliczenie odległości kwartetu $wymagałoby$ $,$ jest liści

W przypadku drzew binarnych znaleziono lepsze algorytmy do obliczania odległości

${\ Displaystyle O (N ^ {2})}$ czas
${\ Displaystyle O (N \ log ^ {2} N)}$ czas

I

${\ Displaystyle O (N \ log N)}$ czas

Gerth Stølting Brodal i in. znalazł algorytm, który potrzebuje $obliczenie$ $na$ kwartetu między dwoma rozgałęzionymi drzewami, drzew jest dostępny w C, perlu i pakiecie R Quartet .

Bibliografia _ McMorris, Francja; Meacham, Christopher A. (1985). „Porównanie nieukierunkowanych drzew filogenetycznych opartych na poddrzewach czterech jednostek ewolucyjnych”. Zoologia systematyczna . 34 (2): 193–200. doi : 10.2307/2413326 . JSTOR 2413326 .
Bibliografia _ J. Tsang; PE Kearney; M. Li. (11 stycznia 2000). „Obliczanie odległości kwartetu między drzewami ewolucyjnymi” . Materiały z jedenastego dorocznego sympozjum ACM-SIAM na temat algorytmów dyskretnych . Nowy Jork : prasa ACM: 285–286.
^ Brodal, Gerth Stølting; Fagerberg, Rolf; Pedersen, Christian NS (2001). „Obliczanie odległości kwartetu między drzewami ewolucyjnymi w czasie ${\ Displaystyle O (n \ log ^ {2} n)}$ ”. Algorytmy i obliczenia . Notatki z wykładów z informatyki. Tom. 2223. s. 731–742. doi : 10.1007/3-540-45678-3_62 . ISBN 978-3-540-42985-2 .
^ Brodal, Gerth Stølting ; Rolfa Fagerberga; Christian Nørgaard Storm Pedersen (2003). „Obliczanie odległości kwartetu między drzewami ewolucyjnymi w czasie ${\ Displaystyle O (n \ log n)}$ ”. Algorytmika . 38 (2): 377–395. doi : 10.1007/s00453-003-1065-y . S2CID 6911940 .
^ Brodal, Gerth Stølting ; Rolfa Fagerberga; T Mailund; Christiana Norgaarda Storma Pedersena; Piasek (2013). „Wydajne algorytmy obliczania odległości trypletu i kwartetu między drzewami o dowolnym stopniu” (PDF) . Materiały z dwudziestego czwartego dorocznego sympozjum ACM-SIAM na temat algorytmów dyskretnych . SYJAM: 1814–1832. doi : 10.1137/1.9781611973105.130 . ISBN 978-1-61197-251-1 .

[eastbrook1985-1] Bibliografia _ McMorris, Francja; Meacham, Christopher A. (1985). „Porównanie nieukierunkowanych drzew filogenetycznych opartych na poddrzewach czterech jednostek ewolucyjnych”. Zoologia systematyczna . 34 (2): 193–200. doi : 10.2307/2413326 . JSTOR 2413326 .

[2] Bibliografia _ J. Tsang; PE Kearney; M. Li. (11 stycznia 2000). „Obliczanie odległości kwartetu między drzewami ewolucyjnymi” . Materiały z jedenastego dorocznego sympozjum ACM-SIAM na temat algorytmów dyskretnych . Nowy Jork : prasa ACM: 285–286.

[3] Brodal, Gerth Stølting; Fagerberg, Rolf; Pedersen, Christian NS (2001). „Obliczanie odległości kwartetu między drzewami ewolucyjnymi w czasie ${\ Displaystyle O (n \ log ^ {2} n)}$ ”. Algorytmy i obliczenia . Notatki z wykładów z informatyki. Tom. 2223. s. 731–742. doi : 10.1007/3-540-45678-3_62 . ISBN 978-3-540-42985-2 .

[4] Brodal, Gerth Stølting ; Rolfa Fagerberga; Christian Nørgaard Storm Pedersen (2003). „Obliczanie odległości kwartetu między drzewami ewolucyjnymi w czasie ${\ Displaystyle O (n \ log n)}$ ”. Algorytmika . 38 (2): 377–395. doi : 10.1007/s00453-003-1065-y . S2CID 6911940 .

[5] Brodal, Gerth Stølting ; Rolfa Fagerberga; T Mailund; Christiana Norgaarda Storma Pedersena; Piasek (2013). „Wydajne algorytmy obliczania odległości trypletu i kwartetu między drzewami o dowolnym stopniu” (PDF) . Materiały z dwudziestego czwartego dorocznego sympozjum ACM-SIAM na temat algorytmów dyskretnych . SYJAM: 1814–1832. doi : 10.1137/1.9781611973105.130 . ISBN 978-1-61197-251-1 .