Dynamic Programming Based Approximation Algorithms for Sequence Alignment with Constraints.
Abdullah N. ArslanÖmer EgeciogluPublished in: INFORMS J. Comput. (2004)
Keyphrases
- sequence alignment
- approximation algorithms
- dynamic programming
- np hard
- special case
- pairwise
- worst case
- precedence constraints
- vertex cover
- minimum cost
- set cover
- network design problem
- primal dual
- protein sequences
- phylogenetic analysis
- binding sites
- approximation ratio
- amino acids
- linear program
- open shop
- linear programming
- upper bound
- multiple sequence alignment
- randomized algorithms
- multiple alignment
- comparative genomics
- undirected graph
- protein structure
- greedy algorithm
- optimal solution
- reinforcement learning
- genetic algorithm