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.

Algorithms in Support of the Human Genome Project

Dan Gusfield, John Kececioglu, R. Ravi, Jim Knight
Department of Computer Science, University of California, Davis, CA 95616. gusfield@cs.ucdavis.edu

And

Gene Lawler, Archie Cobbs
Department of Computer Science, University of California, Berkeley, CA

Our research covers a wide variety of algorithmic and data structure issues involved in obtaining and analyzing sequence data, in searching databases, in reconstructing evolutionary history from sequence data or from genome rearrangements. The work is both theoretical and applied, and is divided into the following thirteen papers and three programs that we worked on in the past year. Below are the titles of these efforts, which give a fair indication of the thrust and content of our work.

Sequence analysis and database searching:

• Fast identification of approximately matching substrings - Cobbs
• Improved approximate matching over suffix trees - Cobbs
• Faster implementation of a common superstring heuristic - Gusfield
• Uniform preprocessing for linear time string matching - Gusfield
• Approximate algorithms for multiple sequence alignment - Bafna, Lawler, Pevzner
• Computational experience with a branch-and-bound algorithm for maximum-trace multiple sequence alignment - Kececioglu

Genome Rearrangements:

• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement- Kececioglu, Sankoff
• Efficient Bound for oriented chromosome-inversion distance - Kececioglu, Sankoff
• Of Mice and Men: Algorithms for evolutionary distances between genomes with translocation and inversion - Kececioglu and Ravi
• Reconstructing a history of recombinations from a set of sequences - Kececioglu and Gusfield

Sequence Reconstruction:

• Approximate algorithms for multiple alignment to a phylogenetic tree - Jian, Lawler, Wang
• Approximation algorithms for tree alignment - Kececioglu, Ravi

Algorithms for laboratory support:

• A problem in the design of oligo probes for disease detection and in primer selection for PCR- Ravi, Gusfield

Software Development:

• FLASH: A software tool to find secondary structures and motifs - Knight
• A visual tool for construction of secondary structure - Knight
• Wparal - parametric alignment in MS-Windows.