Biomedical Engineering Reference
In-Depth Information
assigned weights. We discuss subsequently the first iteration in constructing the guide
tree in detail assuming that we have
N
OTUs.
We denote by
D
ij
the distance between OTUs
i
and
j
. Note that all these pair-
wise distances have been computed through the dynamic programming algorithm in
Section 8.2.1. We denote by
L
ab
the branch length between nodes
a
and
b
. The pur-
pose of the neighbor-joining method is to compute all the branch lengths from the
pairwise distances.
Our first task is to compute the sum of branch lengths of the tree in Figure 8.1
a
.
We represent this by
S
0
.
N
1
i<j
1
S
0
=
L
iX
=
D
ij
(8.1)
N
−
i
=
1
We can derive Eq. (8.1) in the following way. We can write the distances from OTU
1 to all other OTUs as:
N
D
1
j
=
(L
1
X
+
L
2
X
)
+
(L
1
X
+
L
3
X
)
+···+
(L
1
X
+
L
NX
)
(8.2)
j
=
2
N
N
D
1
j
=
(N
−
1
)L
1
X
+
L
kX
(8.3)
j
=
2
k
=
2
Equation (8.2) follows from the fact that a distance like
D
12
is essentially the
sum
L
1
X
+
L
2
X
following the tree branches. The sum
i<j
D
ij
is the sum of all the
pairwise distances such that
i < j
, in other words, each distance is counted only once.
Similarly, we can write
N
N
D
2
j
=
(N
−
2
)L
2
X
+
L
kX
j
=
3
k
=
3
The equations for
j
=
4
D
3
j
and so on can be written in a similar way. The following
equation results from adding the left-hand and right-hand sides of the earlier equations
and doing some simplifications.
N
D
ij
=
−
(N
1
)
L
ix
(8.4)
i<j
i
=
1
Hence, Eq. (8.1) follows from Eq. (8.4).
Our next task is to identify a pair of OTUs so that the tree has the smallest sum of
branch lengths. The OTUs 1 and 2 indicate this pair in Figure 8.1. Note that there are
N(N
1
)/
2 ways of choosing this pair and we assume that OTUs 1 and 2 as neighbors
give the smallest sum of branch lengths. Once the pair is chosen, we consider it as a
−
Search WWH ::
Custom Search