Biology Reference
In-Depth Information
For our main problem of
CpG
identification, the probability
P
(
x
)
of a DNA
sequence of nucleotides
x
x
l
is not of much interest by itself but we will
need it to compute the
posterior probabilities P
=
x
1
x
2
···
l
,
that symbol
x
t
in the observed sequence was emitted from state
k
, which can then be
used for decoding.
Since
(π
t
=
k
|
x
),
k
∈
Q
,
t
=
1
,
2
,...,
P
(
x
,π
t
=
k
)
P
(π
t
=
k
|
x
)
=
,
(9.3)
P
(
x
)
we need a recursive algorithm for computing
P
(
x
,π
t
=
k
)
. The Markov property of
the hidden process makes this possible:
P
(
x
,π
t
=
k
)
=
P
(
x
1
x
2
···
x
t
,π
t
=
k
)
P
(
x
t
+
1
x
t
+
2
···
x
l
|
x
1
x
2
···
x
t
,π
t
=
k
)
=
P
(
x
1
x
2
···
x
t
,π
t
=
k
)
P
(
x
t
+
1
x
t
+
2
···
x
l
|
π
t
=
k
).
(9.4)
The first line is a direct application of the conditional probability formula where the
probability that
x
is generated with
k
at time
t
is given as the product of the
probabilities of the following events: (1) symbols
x
1
x
2
···
π
t
=
x
t
are emitted up to time
t
and the process is in state
k
at time
t
, and (2) conditioned upon the event (1), the rest
of the emitted sequence is
x
t
+
1
x
t
+
2
···
x
l
. The second line follows from the Markov
property of the hidden process and restates that the probability to emit the sequence
x
t
+
1
x
t
+
2
···
x
l
depends only on the state of the process at time
t
.
Notice that the
P
(
x
1
x
2
···
x
t
,π
t
=
k
)
are exactly the probabilities
f
k
(
t
)
, which are
computed from the forward algorithm. Denote
b
k
(
t
)
=
P
(
x
t
+
1
x
t
+
2
···
x
l
|
π
t
=
k
)
.
Equation (
9.4
) can now be re-written as
P
(
x
,π
t
=
k
)
=
f
k
(
t
)
b
k
(
t
).
(9.5)
are computed by the
backward algorithm
.Webeginby
initializing the algorithm for
t
The probabilities
b
k
(
t
)
=
l
where, since
x
l
is the last observed symbol,
π
l
+
1
=
E
is the end state (that does not emit a symbol). Thus
b
k
(
)
=
(π
l
+
1
=
l
P
|
π
l
=
)
=
,
∈
E
Q
, since the sequence goes to the end state E with probability 1.
Once we know
b
k
(
k
1
k
l
)
for all
k
∈
Q
, for any of the values
t
=
l
−
1
,
l
−
2
,...,
1
we can compute
b
j
(
t
)
=
P
(
x
t
+
1
x
t
+
2
···
x
l
|
π
t
=
j
)
=
(π
t
+
1
=
|
π
t
=
)
e
k
(
x
t
+
1
)
(
x
t
+
2
···
x
l
|
π
t
+
1
=
)
P
k
j
P
k
k
∈
Q
=
a
jk
e
k
(
x
t
+
1
)
b
k
(
t
+
1
).
k
∈
Q
The justification is as follows: At time
t
+
1 the process can transition from
j
to any
other state
k
∈
Q
(this happens with probability
a
jk
)
,emit
x
t
+
1
(this happens with
probability
e
k
(
x
t
+
1
))
, and, being in state
k
at time
t
+
1, emit the rest of the sequence
x
t
+
2
···
x
l
(which happens with probability
b
k
(
t
+
1
))
.
Search WWH ::
Custom Search