A polyhedral approach to sequence alignment problems

DOI10.1016/S0166-218X(00)00194-3zbMath0998.92017OpenAlexW2125372717WikidataQ56977389 ScholiaQ56977389MaRDI QIDQ1585327

Petra Mutzel, Knut Reinert, Martin Vingron, Kurt Mehlhorn, Hans-Peter Lenhof, John D. Kececioglu

Publication date: 13 November 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00194-3

zbMATH Keywords

multiple sequence alignmentbranch-and-cutcomputational biologyRNA sequence alignment

Mathematics Subject Classification ID

Applications of graph theory (05C90) Combinatorial optimization (90C27) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20) Complexity and performance of numerical algorithms (65Y20)

Related Items (13)

DCA based algorithms for multiple sequence alignment (MSA) ⋮ On some optimization problems in molecular biology ⋮ Novel evolutionary models and applications to sequence alignment problems ⋮ Fast separation for the three-index assignment problem ⋮ Mathematical programming in computational biology: an annotated bibliography ⋮ Heuristic algorithms in computational molecular biology ⋮ New formulations of the multiple sequence alignment problem ⋮ Partially local multi-way alignments ⋮ The maximum weight trace alignment merging problem ⋮ DC Programming and DCA for Challenging Problems in Bioinformatics and Computational Biology ⋮ Near optimal multiple alignment within a band in polynomial time ⋮ Exact Multiple Sequence Alignment by Synchronized Decision Diagrams ⋮ A simple and space-efficient fragment-chaining algorithm for alignment of DNA and protein sequences

Uses Software

• LEDA
• ABACUS
• RNAlign

Cites Work

• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• Locally optimal subalignments using nonlinear similarity functions
• The ellipsoid method and its consequences in combinatorial optimization
• Generalized sequence alignment and duality
• Multiple sequence comparison and consistency on multipartite graphs
• A Cutting Plane Algorithm for the Linear Ordering Problem
• The Context Dependent Comparison of Biological Sequences
• Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems
• Facet of regular 0–1 polytopes
• A New Algorithm for Generating All the Maximal Independent Sets
• On Linear Characterizations of Combinatorial Optimization Problems
• Properties of vertex packing and independence system polyhedra
• Multiple DNA and protein sequence alignment based on segment-to-segment comparison.
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A polyhedral approach to sequence alignment problems