Distancia del cuarteto

La distancia de 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. ${\displaystyle O(N^{4})}$ ${\displaystyle N}$

Para los árboles binarios, se han encontrado mejores algoritmos para calcular la distancia en

• ${\displaystyle O(N^{2})}$tiempo ^[2]
• ${\displaystyle O(N\log ^{2}N)}$tiempo ^[3]

y

• ${\displaystyle O(N\log N)}$tiempo ^[4]

Gerth Stølting Brodal et al. encontraron un algoritmo que toma tiempo para calcular la distancia de cuarteto entre dos árboles multifurcantes cuando es el grado máximo de los árboles, ^[5] al que se puede acceder en C, Perl y el paquete R Quartet. ${\displaystyle O(DN\log N)}$ ${\displaystyle D}$

Referencias

1. 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.
2. Bryant, D.; J. Tsang; PE Kearney; M. Li. (11 de enero de 2000). "Cálculo de la distancia de cuarteto entre árboles evolutivos". Actas del undécimo simposio anual ACM-SIAM sobre algoritmos discretos . Nueva York : ACM Press: 285–286.
3. Brodal, Gerth Stølting; Fagerberg, Rolf; Pedersen, Christian NS (2001). "Cálculo de la distancia de cuarteto entre árboles evolutivos en el tiempo ". Algoritmos y computación . Apuntes de clase en informática. Vol. 2223. págs. 731–742. doi :10.1007/3-540-45678-3_62. ISBN ${\displaystyle O(n\log ^{2}n)}$ 978-3-540-42985-2.
4. Brodal, Gerth Stølting ; Rolf Fagerberg; Christian Nørgaard Tormenta Pedersen (2003). "Cálculo de la distancia del cuarteto entre árboles evolutivos en el tiempo ". Algorítmica . 38 (2): 377–395. doi :10.1007/s00453-003-1065-y. S2CID  6911940. ${\displaystyle O(n\log n)}$
5. Brodal, Gerth Stølting ; Rolf Fagerberg; T Mailund; Christian Nørgaard Storm Pedersen; A Sand (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-0-2013-001-001 978-1-61197-251-1.