Name
Abstract | ||
|---|---|---|
Multiple sequence alignment is a central problem in Bioinformatics. A known integer programming approach is to apply branch-and-cut to exponentially large graph-theoretic models. This paper describes a new integer program formulation that generates models small enough to be passed to generic solvers. The formulation is a hybrid relating the sparse alignment graph with a compact encoding of the alignment matrix via channelling constraints. Alignments obtained with a SAT-based local search algorithm are competitive with those of state-of-the-art algorithms, though execution times are much longer. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/978-3-540-45193-8_83 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
data structure,branch and cut,objective function,genetic algorithm,local search algorithm,multiple sequence alignment,multiple alignment | Graph theory,Constraint satisfaction,Mathematical optimization,Search algorithm,Computer science,Algorithm,Integer programming,Local search (optimization),Multiple sequence alignment,Constrained optimization,Dense graph | Conference |
Volume | ISSN | Citations |
2833 | 0302-9743 | 4 |
PageRank | References | Authors |
0.45 | 4 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Steven David Prestwich | 1 | 608 | 47.15 |
| Desmond G. Higgins | 2 | 1263 | 383.91 |
| Orla O’Sullivan | 3 | 4 | 0.45 |