 |
|
 |
|
 |
|
| Archive |
|
Sponsored
by the U.S. Department of
Energy Human Genome Program
|
DOE Human Genome Program Contractor-Grantee Workshop IV
Santa Fe, New Mexico, November 13-17, 1994
|
Introduction to the Workshop
The electronic form of this document may be cited in the following style: 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 AlignmentGary 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.
|
