Related Experiment Videos
Finite-state models in the alignment of macromolecules
L Allison1, C S Wallace, C N Yee
1Department of Computer Science, Monash University, Australia.
Journal of Molecular Evolution
|July 1, 1992
Summary
Minimum message length (MML) encoding provides a powerful method for comparing biological sequences. This study applies MML to DNA sequence alignment, favoring more complex models for improved accuracy.
Area of Science:
- Computational Biology
- Bioinformatics
- Machine Learning
Background:
- Minimum Message Length (MML) encoding is an inductive inference technique with significant theoretical and practical benefits.
- MML enables the calculation of posterior odds-ratios between competing hypotheses, facilitating objective model comparison.
- This method is particularly useful for analyzing relationships between biological sequences, such as DNA.
Purpose of the Study:
- To apply Minimum Message Length (MML) encoding to the problem of aligning and relating biological sequences, specifically DNA.
- To compare the 'relatedness' theory (r-theory) against the null hypothesis of unrelated sequences.
- To evaluate different models of sequence relation or mutation, including one-, three-, and five-state models.
Main Methods:
- Utilized Minimum Message Length (MML) encoding for sequence comparison.
- Developed and compared one-, three-, and five-state models representing sequence relatedness and mutation processes.
- These models correspond to different cost functions for insertions and deletions, including linear and piecewise linear.
- Described parameter estimation and objective model validity testing procedures.
- Implemented and tested a fast, approximate MML string comparison algorithm.
Main Results:
- The study demonstrates that MML can calculate probabilities of various sequence alignments when sequences are related.
- Objective model testing on real DNA and artificial data was performed.
- Tests on real DNA sequences indicate that the three- or five-state models provide a better fit than the one-state model.
- Analyses on artificial data highlight the inferential limitations under different scenarios.
Conclusions:
- Minimum Message Length (MML) encoding is a robust framework for biological sequence alignment and relationship inference.
- More complex models (three- and five-state) are empirically supported over simpler models for real DNA data.
- The developed approximate algorithm offers an efficient approach for MML-based sequence comparison.