Lecture in Computational Biology on 20 March 2002
Content of a lecture on 20 March 2002
The argument of this lecture was once again
the study of
some problems of similarity among strings.
We remember that there are three main kinds of such problems:
In previous lectures we faced the first case (global similarity),
first introducing a rigorous formalization of the problem in terms
of alignments and scores of alignments,
and then providing an efficient Dynamic Programming algorithm for the
Today we have seen as the notion of alignment is also suitable in
the other two sequence comparison problems, modulo small differences
in the way we compute the score of the alignments.
we discovered that essentially the same Dynamic Programming approach
suffices in solving also the new string comparison problems.
- global similarity;
- local similarity;
- semiglobal similarity.
No homeworks were assigned.
An extremely good introduction to the problem of the similarity among
two or more strings
is given in Chaper 3 of the book recommended as a companion for this
- J.C. Setubal and J. Meidanis,
Introduction to Computational Molecular Biology,
PWS Publishing Company.
An International Thomson Publishing Company, (1997)
Have a nice reading and self-study!
© Dipartimento di Matematica - Università di Trento