Algorithms in Support of the Human Genome Project[1]

Dan Gusfield, Jim Knight, Kevin Murphy, Paul Stelling, Lushen Wang

Department of Computer Science, University of California, Davis, CA 95616. gusfield@cs.ucdavis.edu; and Archie Cobbs, Paul Horton, Gene Lawler, 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 sequences from hybridization data, in reconstructing evolutionary history from sequence data or from genome rearrangements, in studying repeated structures in biological sequences. The work is both theoretical and applied, and has produced more than twenty papers and five computer programs in the last two years. Below is a selected listing of some of the recent efforts supported by the grant.

Sequence analysis and database searching:

• Fast identification of approximately matching substrings - Cobbs Published in the Proceedings of the 6th Annual symposium on combinatorial pattern matching, July 1995.

• Improved approximate matching over suffix trees - Cobbs Published in the Proceedings for the 5th Annual symposium on combinatorial pattern matching, June 1994.

• Uniform preprocessing for linear time string matching - Gusfield Dimacs Technical report, December 1995.

• Approximate algorithms for multiple sequence alignment - Bafna, Lawler, Pevzner Published in the Proceedings of the 5th Annual symposium on combinatorial pattern matching, June 1994.

• Computational experience with a branch-and-bound algorithm for maximum-trace multiple sequence alignment - Kececioglu Published in the Proceedings of the 5th Annual symposium on combinatorial pattern matching, June 1994.

• Automata-Theoretic Models of Mutation and Alignment- David Searls and Kevin Murphy Published in the Proceedings of the 3rd International conference on Intelligent Systems in Molecular Biology. July, 1995.

• Efficient Parametric and Inverse Parametric Sequence Alignment with XPARAL - Gusfield and Stelling. To appear in Methods of Enzymology issue on Computer Methods for Macromolecular Sequence Analysis edited by R. Doolittle.

• A Branch and Bound Algorithm for Local Multiple Alignment - Horton. To appear in the Proceedings of the Pacific Symposium on Biocomputing January 1996.

• Prioritized Suffix Tree Based Approximate Search - Cobbs Manuscript June 1995.

• Constructing Additive Trees when the Error is Small- Wang Manuscript, August 1995.

• An Efficiently Solved Traveling Salesman Problem arising from Sequencing by Hybridization. Gusfield, Stelling, Wang. Manuscript, October 1995.

• Optimal Alignments in Linear Space Using Automaton-derived Cost Functions - Murphy. Manuscript July 1995.

• Passively Learning Finite Automata: A Survey - Murphy. Manuscript, October 1995.

Genome Rearrangements:

• Efficient Bound for oriented chromosome-inversion distance - Kececioglu, Sankoff In Proceedings of the 5th Symposium on Combinatorial Pattern Matching, June 1994.

• Of Mice and Men: Algorithms for evolutionary distances between genomes with translocation and inversion - Kececioglu and Ravi Published in the Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, January 1995.

Sequence Reconstruction:

• Approximate algorithms for multiple alignment to a phylogenetic tree - Jiang, Lawler, Wang. To appear in SIAM Journal on Computing.

• Improved Algorithms for Tree Alignment - Wang and Gusfield Manuscript, October 1995.

• Approximation algorithms for multiple sequence alignment under a fixed evolutionary tree - Ravi and Kececioglu. Proceedings of the 6th Annual symposium on combinatorial pattern matching, July, 1995.

[1]Supported by DOE Grant DE-FG03-9OER60999