Phylogenetic Tree Reconstruction: Geometric Approaches - Mathematical Concepts and Methods in Modern Biology - page 324

illustrated in Figure 10.6 above, where each triangle represents a clade , that is, a
subtree arising from a node and all its descendants and edges connecting them; here
it could be a single leaf. For clades A D , an NNI move is essentially a move

on a quartet, exchanging the neighbor of one cherry for a neighbor of the other cherry
(see Figure 10.6 ). The SPR moves and TBR moves are more general but can be sim-
ilarly pictured; see, e.g., [ 2 , Section 2.6] for definitions and representative pictures,
or [ 23 , Section 3] for a definition and picture of an SPR move relevant to our later
discussion.

, B , C ,

10.4 NEIGHBOR-JOINING AND BME
10.4.1 Neighbor-Joining
The Neighbor-Joining (NJ) Algorithm [ 16 ] takes as input a dissimilarity map c ∈

n
2

,ω) ∈ T n ,
by iteratively picking cherries out of X . There are three essential steps in the NJ
Algorithm:

and builds an edge-weighted unrooted binary phylogenetic X -tree ( T

R

1. Pick a cherry { , } , ∈

X .
2. Create a node a i , j joining leaves i and j .
3. Compute the distances from other nodes (including i

i j , for leaves i j

j and all other leaves in
X ) to the new node a i , j (and so produce a new dissimilarity map).

,

If | X | > 3, one then continues the procedure by eliminating { i , j } from the set of leaves

X (i.e., replace by a i , j in the set X ) and seeking the next cherry in the remaining

set of leaves to join, until the total number of remaining leaves n is 3. The result is
an edge-weighted unrooted binary phylogenetic X -tree. Visually, one can proceed by
picturing a star tree on

{ i , j }

-leaves and seeing the NJ Algorithm as a set of instructions
for successively splitting off leaves onto their own branches (see Figure 10.7 ).
The key component of the NJ Algorithm is the method for picking cherries, accom-
plished by the Q -criterion, described in Theorem 10.2 below. The formulation of the
cherry-picking step of the NJ Algorithm, as a problem of minimizing the Q -values,
comes from a reworking of [ 16 ]by[ 24 ].
Theorem 10.2.

| X |

(Cherry-picking criterion (also known as Q -criterion) [ 16 , 24 ])

n
2

∈ R ∈ T n with leaf set X, and define the

Let c beatreemetricforatreeT

n × n-matrix Q c with entries:

n n

Q c ( i , j ) = ( n − 2 ) c i , j − c i , k − c k , j = ( n − 4 ) c i , j − c i , k − c k , j . (10.3)

k = k = k = j k = i 1 1

i ∗ , j ∗ }⊂ i ∗ , j ∗ ) Then any pair of leaves { X, forwhich Q c ( is minimal, is a cherry in

thetreeT.