Integer linear programming models for multiple sequence alignment

Abstract

Trobar una solució òptima per a una instància de problema d’alineació de seqüències múltiples per a més de dues seqüències és un problema d’optimització dur que és computacionalment car, fins i tot per a algunes seqüències de longitud moderada. En conseqüència, la investigació sobre l'alineació de seqüències múltiples s'ha centrat principalment en mètodes heurístics. No obstant això, els avenços recents en solucionadors de programació lineal enters han permès trobar solucions exactes i òptimes a instàncies de problemes d'alineació de seqüències múltiples per a diverses seqüències de longitud moderada.

Encontrar una solución óptima para una instancia de problema de alineación de secuencias múltiples para más de dos secuencias es un problema de optimización difícil que es prohibitivamente costoso desde el punto de vista computacional, incluso para algunas secuencias de longitud moderada. En consecuencia, la investigación sobre la alineación de secuencias múltiples se ha centrado principalmente en los métodos heurísticos. Sin embargo, los avances recientes en solucionadores para la programación lineal de enteros han hecho posible encontrar soluciones exactas y óptimas para los casos de problemas de alineación de secuencias múltiples para varias secuencias de longitud moderada.

Finding an optimal solution to a multiple sequence alignment problem instance for more than two sequences is a hard optimization problem that is prohibitively computationally expensive, even for a few sequences of moderate length. Consequently, research on multiple sequence alignment has mainly focused on heuristic methods. However, recent advances in solvers for integer linear programming have made it possible to find exact, optimal solutions to multiple sequence alignment problem instances for several sequences of moderate length.