Algorithms in bioinformatics (CSI 5126)=1Please don't print these lecture notes unless you really need

1Algorithms in bioinformatics (CSI 5126)Marcel Turcotte(turcotte@site.uottawa.ca)School of Information Technology and EngineeringUniversity of OttawaCanadaOctober 2, 20091Please don’t print these lecture notes unless you really need to!Marcel Turcotte (turcotte@site.uottawa.ca) CSI 5126. Algorithms in bioinformaticsPlanI String algorithmsI MotivationI NotationI Glimpse of Boyer-Moore string matching algorithmI Su x treesI De nitionI Na ve construction algorithmI Daniela Cernea’s Java libraryMarcel Turcotte (turcotte@site.uottawa.ca) CSI 5126. Algorithms in bioinformaticsMotivationI The simplest model of a macromolecule is a string. Yet, thislevel of abstraction is su cient for a considerably largenumber of applicationsI The size of the biological databases has been doubling every12 to 18 months for the last few yearsI Millions of queries are made to (static) databasesI Instances of exact and approximate string matchingproblems are solved as sub-tasks of several bioinformaticsapplications, such as the DNA assembly processI Natural transition between approximate string matching andmolecular sequence alignmentsMarcel Turcotte (turcotte@site.uottawa.ca) CSI 5126. Algorithms in bioinformaticsExamples of Problems on Strings1. Exact string matching: nding all occurrences of a string in atext2. Approximate string matching: nd all positions in a text wherea pattern occurs, allowing for a certain number of mismatches3. Longest common ...