A polyhedral approach to sequence alignment problems [Elektronische Ressource] / von Knut Reinert

A Polyhedral Approachto Sequence Alignment ProblemsDissertationzur Erlangung des Gradesdes Doktors der Ingenieurswissenschaften (Dr.-Ing.)der Technischen Fakult atder Universit at des SaarlandesvonKnut ReinertSaarbruc ken5. August 1999Datum des Kolloqiums: 5. August 1999Dekan der technischen Fakult at:Professor Dr. Wolfgang PaulGutachter:Professor Dr. Kurt Mehlhorn, MPI fur Informatik, Saarbruc ken Dr. John Kececioglu, University of Georgia, Athens, USA23AbstractWe study two problems in sequence alignment both from a theoretical and a practicalpoint of view. For the rst time in sequence alignment, we use tools from combina-torial optimization to develop branch-and-cut algorithms that solve these problemse cien tly. The Generalized Maximum Trace formulation captures several forms ofmultiple sequence alignment problems in a common framework, among them is theoriginal formulation of Maximum Trace. The Structural Maximum Trace Problemcaptures the comparison of RNA molecules on the basis of their primary sequenceand their secondary structure. For both problems we derive a characterization interms of graphs which we use to reformulate the problems in terms of integer linearprograms. We then study the polytopes (or convex hulls of all feasible solutions)associated with the integer linear program for both problems.