La distancia del cuarteto [1] es una forma de medir la distancia entre dos árboles filogenéticos . Se define como el número de subconjuntos de cuatro hojas que no están relacionados por la misma topología en ambos árboles.
Calcular la distancia del cuarteto
El cálculo más sencillo de la distancia del cuarteto requeriría tiempo, donde es el número de hojas de los árboles.
Para árboles binarios, se han encontrado mejores algoritmos para calcular la distancia en
y
- tiempo [4]
Gerth Stølting Brodal y col. encontré un algoritmo que toma tiempo para calcular la distancia del cuarteto entre dos árboles multifurcantes cuando es el grado máximo de los árboles, [5] que es accesible en C, perl y el paquete R Quartet .
Referencias
- ^ Estabrook, George F .; McMorris, FR; Meacham, Christopher A. (1985). "Comparación de árboles filogenéticos no dirigidos basados en subárboles de cuatro unidades evolutivas". Zoología sistemática . 34 (2): 193–200. doi : 10.2307 / 2413326 . JSTOR 2413326 .
- ^ Bryant, D .; J. Tsang; PE Kearney; M. Li. (11 de enero de 2000). "Calculando la distancia cuarteto entre árboles evolutivos" . Actas del XI Simposio Anual ACM-SIAM sobre Algoritmos Discretos . NY : ACM Press: 285–286.
- ^ Brodal, Gerth Stølting; Fagerberg, Rolf; Pedersen, Christian NS (2001). "Calcular la distancia del cuarteto entre árboles evolutivos en el tiempo." Algoritmos y Computación . Lecture Notes in Computer Science. 2223 pp 731-742... Doi : 10.1007 / 3-540-45678-3_62 . ISBN 978-3-540-42985-2.
- ^ Brodal, Gerth Stølting ; Rolf Fagerberg; Christian Nørgaard Storm Pedersen (2003). "Calcular la distancia del cuarteto entre árboles evolutivos en el tiempo". Algorithmica . 38 (2): 377-395. Doi : 10.1007 / s00453-003-1065-y . S2CID 6911940 .
- ^ Brodal, Gerth Stølting ; Rolf Fagerberg; T Mailund; Christian Nørgaard Storm Pedersen; Una arena (2013). "Algoritmos eficientes para calcular la distancia de triplete y cuarteto entre árboles de grado arbitrario" (PDF) . Actas del Vigésimo Cuarto Simposio Anual ACM-SIAM sobre Algoritmos Discretos . SIAM: 1814–1832. doi : 10.1137 / 1.9781611973105.130 . ISBN 978-1-61197-251-1.