Lecture in Computational Biology on 27 March 2002
Content of a lecture on 27 March 2002
In this lecture, we have introduced the notion of suffix tree trying also to indicate some of the possible uses of this data structure. The main body of the whole lecture has been the exposition of Ukkonen's linear time algorithm for constructing the suffix tree of any given string (over a finite alphabet). We have followed closely the exposition of this algorithm as given in Chapter 6 of the following book.
We proved the NP-completeness of the Double Digest Problem in Physical Mapping of chromosomes.
The algorithm we have seen today is quite complex. Maybe I should have spared you (and myself), but the point is that suffix trees are really important. Since the lecture has now been played, I would suggest you to read a description of Ukkonen's algorithm, to fix the ideas and fit the last details missed. It would also pay a lot to browse the many applications of suffix trees as listed in some text, read just the statement of the problems, and try to see how to solve the problem by means of suffix trees working on your own. For the kind of homeworks suggested here above the following book could serve as a companion.
Enjoy your NP-completeness proofs!
© Dipartimento di Matematica - Università di Trento