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 Applications of su x trees (ST)I Generalized su x treesI Lowest common ancestor (LCA)I Applications of LCA + STMarcel Turcotte (turcotte@site.uottawa.ca) CSI 5126. Algorithms in bioinformatics11 9monotonous$$ us$1 monotonous$ r s$ 10no otonous$5us$us$ notonous$87 tonous$3us$tonous$462Marcel Turcotte (turcotte@site.uottawa.ca) CSI 5126. Algorithms in bioinformaticsSummaryI A su x tree can be built in linear time and spaceI Su x trees were developed to determine if a string P occursin a text T in time proportional tojPj (after pre-processing,i.e. building the tree)I Indeed, P is a substring of T i P is a pre x of a su xof TI To locate P, it su ce to follow a unique path from the rootof the tree up to a node, explicit or implicit, that correspondsto the end of the pattern. This takes time proportional to thelength of the patternI Nowadays, su x tree based algorithms have beendeveloped to solve a large array of problems for which noe cient algorithm was known. This lecture presentssome of themMarcel Turcotte (turcotte@site.uottawa.ca) CSI 5126. Algorithms in bioinformaticsLongest repeated ...