Workshop on Sequence Alignment

November 10 - 12, 1994
Princeton University, Princeton, NJ

Alberto Apostolico, Purdue,
Principal Advisor:
Russel Doolittle (UCLA Medical School)
Organization Committee:
Stephen Altschul (National Library of Medicine, NIH)
Douglas Brutlag (Biochemistry, Stanford)
John Kececioglu (CS, UC Davis)
Martin Farach (CS, Rutgers)
Raffaele Giancarlo (AT&T Bell Labs)
Daniel Gusfield (CS, UC Davis)
David Lipman (National Library of Medicine, NIH)
Pavel Pevzner (CS, Penn State)
David Sankoff (Centre de Recherches Mathematiques, U. Montreal)
Jeannette Schmidt (Brooklyn Polytechnic)
Martin Vingron (German National Research Ctr. for Computer Science)
Michael Waterman (Math. and Molecular Biology, USC)
Presented under the auspices of the Special Year in Mathematical Support for Molecular Biology.
The Workshop will be held at Princeton University. For the list of events and where they will take place on the Princeton campus, please see the enclosed program.

This workshop will deal with string alignment problems in which one wishes to gain information about a newly sequenced piece of DNA by comparing, or aligning it, with a sequence of known function or structure. Detection of similarity between two different molecular sequences has led to the discovery of shared phenomena. (We have already referred to the discovery that the sequence for platelet derived factor, which causes growth in the body, is 87% identical to the sequence for v-sis, a cancer-causing gene, which led to the discovery that v-sis works by stimulating growth.) The quality of a match between two sequences can be determined by a scoring matrix and a charge for introducing gaps in one of the sequences to get a better match, and then a dynamic programming algorithm can be used to determine the largest number of places where two sequences (gaps added) agree. The theory of random graphs can be used to compare two random sequences and predict how good a match one can expect. Work on determining similarity between pairs of sequences can be expanded to work on detecting matches among a whole cluster of such sequences, and then algorithms or heuristics for determining clique-like structures in corresponding graphs can be useful for finding patterns. In this workshop, we will explore all of these ideas. We will investigate dot-matrix methods, global alignments, local alignments and hash coding methods, multiple alignments, measures of aminoacid similarity, and statistical significance of alignments. This workshop will also be closely coordinated with our Algorithm Implementation Challenge.

Next Next: Call for Participation
Index Workshop Index
DIMACS Home Page
Contacting the Center
Document last modified on November 1, 1994