Algorithmic aspects of some combinatorial problems in bioinformatics [Elektronische Ressource] / vorgelegt von Dirk Bongartz

Algorithmic Aspects of Some CombinatorialProblems in BioinformaticsVon der Fakulta¨t fu¨r Mathematik, Informatik und Naturwissenschaften derRheinisch-Westfa¨lischen Technischen Hochschule Aachen zur Erlangung desakademischen Grades eines Doktors der Naturwissenschaften genehmigteDissertationvorgelegt vonDiplom-InformatikerDirk Bongartzaus ViersenBerichter: Universita¨tsprofessor Dr. Juraj HromkoviˇcUniversita¨tsprofessor Dr. Berthold Vo¨ckingTag der mu¨ndlichen Pru¨fung: 13. April 2006Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfu¨gbar.iiiiiAbstractThe consistently growing field of bioinformatics exhibits the success of coop-erative work in biology and computer science. The interaction between newexperimental techniques gaining more and more data about molecular struc-tures and processes and the knowledge how to prepare, structure, and analyzethis data and even more to predict relations based on this data, is the drivingforce within this field.In this thesis, we study models and combinatorial problems arising fromcurrent bioinformatics research focussing on the algorithmic point of view.Protein structure prediction, sometimes referred to as the “holy grail” ofbioinformatics, is the problem to infer the spatial structure of proteins fromtheiramino-acidsequence. WeproposetwoextensionstothepopularHPmodelfor this task, which significantly improve its applicability in practice.