|
|
- David R. Powell, Lloyd Allison, Trevor I. Dix and David L. Dowe.
- Alignment of Low Information Sequences.
- Australian Computer Science Theory Symposium (CATS98),
pp.215-230, Springer-Verlag (isbn:981-3083-92-1), 1998.
Abstract:
Alignment of two random sequences over a fixed alphabet can be
shown to be optimally done by a Dynamic Programming Algorithm (DPA).
It is normally assumed that the sequences are random and incompressible
and that one sequence is a mutation of the other. However, DNA and
many other sequences are not always random and unstructured,
and the issue arises as how to best align compressible sequences.
Assuming our sequences to be non-random and to emanate from mutations of
a first order Markov model, we note that alignment of high information regions
is more important than alignment of low information regions and arrive at
a new alignment method for low information sequences which performs better
than the standard DPA for data generated from mutations of a
first order Markov model.
Keywords: Sequence Alignment, DNA, Biology, Information Theory.
[preprint.ps]['98],
[preprint.ps]['98].
|
|