Introduction to the Workshop
URLs Provided by Attendees

Abstracts

Mapping

Informatics

Sequencing

Instrumentation

Ethical, Legal, and Social Issues

Infrastructure

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
Cornell University
Ithaca, NY

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.