![]() |
|
| Archive Edition | |
|
Sponsored
by the U.S. Department of
Energy Human Genome Program
|
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. |
Combinatorial algorithms for genome sequence analysisJohn D. Kececioglu Our research has focused on algorithms for genome rearrangements, multiple sequence alignment, and DNA sequence assembly. In genome rearrangements we have developed new algorithms for comparing genomes in terms of inversions [1] and translocations [2], and for reconstructing an evolutionary history for a set of sequences that have evolved by point mutation and recombination [3]. Given the order and orientation of genes on a chromosome from two related organisms, we can efficiently compute upper and lower bounds on the minimum number of inversions to transform one gene order into the other, and determine the minimum by branch-and-bound for problems involving up to 250 genes. Given gene orders from genomes of two multichromosomal organisms, we can efficiently find an evolutionary history that has a near-minimum number of inversions and translocations; when gene orientation is known, the history is guaranteed to be within a factor of 3/2 of optimal; when orientation is unknown, the history is within a factor of 1/2 of optimal. Given a set of sequences that have evolved by point mutation and recombination, we can efficiently identify within the set a pair of protosequences and a history of recombinations that produces the remaining sequences from the protopair such that the maximum cost of any recombination in the history is minimized; when the set has evolved from more than two protosequences, we can efficiently identify a protoset and a recombination history such that the size of the complement of the protoset is within a factor 1/2 of optimal. We are also completing two large implementation projects: a branch-and-bound algorithm for maximum-trace multiple sequence alignment, and a three-phase algorithm for DNA sequence assembly. Maximum trace alignment [4] finds a multiple alignment that is in maximum agreement with a set of candidate pairwise alignments described by dot plots; our algorithm branches on a small set of alignment columns obtained from minimum cuts of a graph, and prunes suboptimal alignments with bounds from a new heuristic. Our three-phase algorithm for sequence assembly uses a decomposition similar to Kececioglu and Myers [5], but solves the fragment orientation and layout problems simultaneously using a relaxation to nonbipartite matchings. This work was supported by a DOE Human Genome Postdoctoral Fellowship. [1] Kececioglu, John and David Sankoff. "Efficient bounds for oriented chromosome-inversion distance." In Proceedings of the 5th Symposium on Combinatorial Pattern Matching, Asilomar, California, Springer-Verlag Lecture Notes in Computer Science, Volume 807, 307-325, June 1994.
|
Send the url of this page to a friend
To read pdf files, download the free Acrobat Reader software.
Last modified: Wednesday, October 29, 2003
Home * Contacts * Disclaimer
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
Genome Program