Back to search

University of Washington

Some computational problems from genomic mapping

Abstract

dc:description.abstract

Modern molecular biology has presented computer science a host of interesting theoretical problems to work on. This thesis presents new algorithms for two computational problems from genomic mapping: The first problem arises in the context of building a restriction fragment map of the genome. The main technical result is a quickly-computed estimate of the a posteriori probability that a pair of clones overlap given their restriction fragment fingerprints. The computed pairwise overlap probabilities are used to search for a locally most-likely clone ordering. A correct or nearly correct clone ordering is needed for the subsequent mapmaking step of fragment identification. The second problem is to find the locations of probes along a genome given separation distance information for certain pairs of probes. The model considered is quite general: The input consists of a collection of probe pairs and an interval for the genomic distance separating each pair. We present an algorithm to determine the set of feasible probe positions up to global reversal and translations. Because the distance intervals are only known with some confidence level, some may be erroneous and must be removed in order to find a consistent map. A novel randomized technique for detecting and removing bad distance intervals is described.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Mumey, Brendan Marshall, 1968-

Subjects

dc:subject × 1

Rights

dc:rights
Statement dc:rights
  • Copyright is held by the individual authors.
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Other
b41695033
40095595
Thesis 46225

Chain of custody

source
Harvested from
University of Washington
Base URL
digital.lib.washington.edu/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Mumey, Brendan Marshall, 1968-. Some computational problems from genomic mapping. 1997. http://hdl.handle.net/1773/6932