Método de uniéndose de vecinos

Basado en una matriz de distancia en relación con el taxón ${\displaystyle r}$, se calcula ${\displaystyle Q}$ como sigue:

${\displaystyle Q(i,j)=(r-2)d(i,j)-\sum _{k=1}^{r}d(i,k)-\sum _{k=1}^{r}d(j,k)}$

donde ${\displaystyle d(i,j)}$ es la distancia entre taxones ${\displaystyle i}$ y ${\displaystyle j}$, y ${\displaystyle k}$ es cualquier otro nodo no ${\displaystyle i}$ ni ${\displaystyle j}$ respectivamente.

Para cada vecino del par que acaba de unirse, utilice la siguiente fórmula para calcular la distancia al nodo nuevo. (Taxones ${\displaystyle f}$ y ${\displaystyle g}$ son los taxones emparejado y ${\displaystyle u}$ es el nodo recién generado):

${\displaystyle d(f,u)={\frac {1}{2}}d(f,g)+{\frac {1}{2(r-2)}}\left[\sum _{k=1}^{r}d(f,k)-\sum _{k=1}^{r}d(g,k)\right]\quad }$

y, por la reflexión:

${\displaystyle d(g,u)=d(f,g)-d(f,u)\quad }$

Para cada taxón no analizado en el paso anterior, se calcula la distancia hasta el nodo nuevo como sigue:

${\displaystyle d(u,k)={\frac {1}{2}}[d(f,k)+d(g,k)-d(f,g)]}$

donde ${\displaystyle u}$ es el nodo nuevo, ${\displaystyle k}$ es el nodo para el que se desea calcular la distancia y ${\displaystyle f}$ y ${\displaystyle g}$ son los miembros del par acaba de unirse.

El cálculo del método de Unión de vecinos para un conjunto de ${\displaystyle r}$ taxones requiere ${\displaystyle r-3}$ iteraciones. En cada paso hay que construir y buscar una matriz ${\displaystyle Q}$.

Inicialmente la matriz ${\displaystyle Q}$ tiene un tamaño ${\displaystyle r\times r}$, de manera que el siguiente paso es ${\displaystyle (r-1)\times (r-1)}$, etcétera. Esto conduce a un algoritmo con una complejidad de tiempo de ${\displaystyle O(r^{3})}$.