inicio

Programación dinámica y complejidad computacional[editar]
El método más directo para producir alineamientos múltiples de secuencias utiliza la técnica de programación dinámica para identificar la solución de alineamiento globalmente óptima. Para las proteínas, este método supone normalmente dos conjuntos de parámetros: una penalización por gap (o hueco) y una matriz de sustitución que asignapuntuaciones o probabilidades al alineamiento de cada posible par de aminoácidos basadas en la similitud de las propiedades químicas de los mismos o en la probabilidad evolutiva de la mutación. Para secuencias de nucleótidos puede usarse una matriz de sustitución, pero dado que sólo hay cuatro caracteres estándar posibles por secuencia, y que los nucleótidos individuales no difieren mucho en suprobabilidad de sustitución, los parámetros para secuencias de ADN y ARN consisten, normalmente, en una penalización por gap, una puntuación positiva para coincidencias de caracteres, y una puntuación negativa para desigualdades.

Para n secuencias individuales, el método requiere construir el equivalente n-dimensional de la matriz formada en el alineamiento estándar de pares de secuencias de laprogramación dinámica. De esta forma, el espacio de búsqueda se incrementa exponencialmente conforme se incrementa n, dependiendo también fuertemente de la longitud de la secuencia. Encontrar de esta forma el óptimo global para n secuencias ha mostrado ser un problema NP-completo.1 2 Los métodos para reducir el espacio de búsqueda efectuando inicialmente alineamientos de pares mediante programacióndinámica sobre cada par de secuencias en el conjunto problema, y buscando sólo el espacio solución cerca de estos resultados (encontrando de forma efectiva la intersección entre trayectorias locales en los alrededores inmediatos de cada solución óptima de alineamiento por pares) representan la técnica de programación dinámica más eficiente. El método denominado "suma de pares" se ha implementado enel software MSA, pero no es todavía práctico para la mayoría de aplicaciones de alineamiento múltiple de secuencias que requieren el alineamiento simultáneo de docenas (y aún de varios centenares) de secuencias. Los métodos de programación dinámica sólo se usan ahora cuando se necesita un alineamiento de muy alta calidad entre un pequeño número de secuencias, así como benchmark estándar en laevaluación de nuevas o mejoradas técnicas heurísticas.

Construcción progresiva del alineamiento[editar]
Un método para realizar una búsqueda heurística del alineamiento es la técnica progresiva (también conocido como método jerárquico o de árbol) que construye un alineamiento múltiple final realizando primero una serie de alineamientos de pares sobre secuencias sucesivamente menos emparentadas.Tales métodos comienzan alineando en primer lugar las dos secuencias más cercanamente relacionadas, para seguir alineando sucesivamente la siguiente secuencia del conjunto problema más emparentada con el alineamiento producido en el paso previo. El par inicial "más relacionado", o emparentado, se determina mediante un método eficiente de categorización (o clustering) tal como el neighbour-joining,basado en una simple búsqueda heurística del conjunto problema con una herramienta como FASTA. Las técnicas progresivas, por tanto, construyen automáticamente tanto un árbol filogenético como un alineamiento.

Una limitación importante de los métodos progresivos es su fuerte dependencia de la asignación inicial del parentesco entre las secuencias, así como de la calidad del alineamiento inicial.De este modo, los métodos son sensibles también a la distribución de las secuencias en el conjunto problema: el rendimiento mejora cuando la cuantificación de la estructura del parentesco entre las secuencias problema compone un gradiente relativamente suave en lugar de encontrarse en categorías distantes. También se degrada significativamente el rendimiento cuando todas las secuencias del...