Algorithms in computational biology

In this thesis we are concerned with constructing algorithms that address problemsof biological relevance. This activity is part of a broader interdisciplinaryarea called computational biology, or bioinformatics, that focuses on utilizingthe capacities of computers to gain knowledge from biological data. Themajority of problems in computational biology relate to molecular or evolutionarybiology, and focus on analyzing and comparing the genetic material oforganisms. One deciding factor in shaping the area of computational biologyis that DNA, RNA and proteins that are responsible for storing and utilizingthe genetic material in an organism, can be described as strings over ♀nite alphabets.The string representation of biomolecules allows for a wide range ofalgorithmic techniques concerned with strings to be applied for analyzing andcomparing biological data. We contribute to the ♀eld of computational biologyby constructing and analyzing algorithms that address problems of relevance tobiological sequence analysis and structure prediction.The genetic material of organisms evolves by discrete mutations, most prominentlysubstitutions, insertions and deletions of nucleotides. Since the geneticmaterial is stored in DNA sequences and reflected in RNA and protein sequences,it makes sense to compare two or more biological sequences to lookfor similarities and di♂erences that can be used to infer the relatedness of thesequences. In the thesis we consider the problem of comparing two sequencesof coding DNA when the relationship between DNA and proteins is taken intoaccount. We do this by using a model that penalizes an event on the DNA bythe change it induces on the encoded protein. We analyze the model in detail,and construct an alignment algorithm that improves on the existing bestalignment algorithm in the model by reducing its running time by a quadraticfactor. This makes the running time of our alignment algorithm equal to therunning time of alignment algorithms based on much simpler models.