DOE Human Genome Program Contractor-Grantee Workshop IV
Santa Fe, New Mexico, November 13-17, 1994
Introduction to the Workshop
URLs Provided by Attendees
- Ethical, Legal, and Social Issues
The electronic form of this document may be cited in the following style:
Human Genome Program, U.S. Department of Energy, DOE Human Genome Program Contractor-Grantee Workshop IV, 1994.
Abstracts scanned from text submitted for November 1994 DOE Human Genome Program Contractor-Grantee Workshop. Inaccuracies have not been corrected.
Bayesian Restoration of a Hidden Markov Chain with Applications to Sequence Alignment
Gary A. Churchill
The problem of assembling DNA sequence fragments generated by a shotgun sequencing project is addressed. In general, the multiple alignment of sequences is recognized to be a difficult and computationally intensive problem. However in the shotgun sequencing context the problem can be reduced to a series of pairwise alignments.
A hidden Markov model describes the process of generating a fragment sequence f by copying a subsequence of the bases in a clone sequence s. When the sequence s and the error rates of the copying process theta are known, each fragment is a conditionally independent realization of this process. We derive the probability distribution of the pairwise sequence alignments between s and individual fragment sequences and describe an algorithm that samples alignments according to this distribution.
This sampling from the distribution of assemblies is one step in a Monte Carlo algorithm for consensus estimation. It is intended to address the problem of ambiguities that will inevitably arise in any assembly and present difficulties for consensus and error rate estimation.
We will indicate how the hidden Markov chain model can be adapted to account for empirical error characteristics of the sequencing process. These extensions of the basic model include context dependent errors (e.g. compressions and homopolymer runs) as well variations in accuracy along the length of individual fragments.
Last modified: Wednesday, October 29, 2003
Home * Contacts * Disclaimer
Document Use and Credits
Publications and webpages on this site were created by the U.S. Department of Energy Genome Program's Biological and Environmental Research Information System (BERIS). Permission to use these documents is not needed, but please credit the U.S. Department of Energy Genome Programs and provide the website http://genomics.energy.gov. All other materials were provided by third parties and not created by the U.S. Department of Energy. You must contact the person listed in the citation before using those documents.
Base URL: www.ornl.gov/hgmis
Site sponsored by the U.S. Department of Energy
Office of Science, Office
of Biological and Environmental Research, Human