FAMSA

Algoritmos para la alineación de secuencia múltiple FAMSA

1. CALCULO DE SIMILITUDES POR PARES

5. REFINAMIENTO ITERATIVO OPCIONAL DEL PERFIL FINAL

La longitud de una subsecuencia comun mas larga se usa para determinar las similitudes por pares de secuencias en el conjunto de entrada. Se calcula utilizando una regla de progrmación dinámica directa.

2. DETERMINACION DE UN ARBOL GUIA

FAMSA utiliza el algoritmo del enlace unico para poder determinar el arbol guia,, esto porque se puede calcular incrementalmente, es muy rapido y tiene resultadols de calidad. la generación de estos requiere solo de espacio O(k) en contraste a O(k^2).

la idea principal es corregir desalineaciones hechas en la primer fase de la alineación del perfil. El algoritmo puede leer hasta 1000 secuencias, primero se escanea el perfil para localizar las columnas que contienen por lo menos una brecha, para luego seleccionar una al azar y dividir el perfil en dos subprofilos. Se elminan las columnas vacías y los subproductos se realinean.

3. FUSION PROGRESIVA DEL PERFIL SEGUN EL ORDEN DEL ARBOL AGUIA

4. DETERMINACION DE LOS TIPOS DE HUECOS Y COSTOS

Esta etapa requiere alineaciones O(k) y se calculan mediante programación dinámica. Al menos la mitad de estas alineaciones son casos degenerados en los que los perfiles constan de una sola secuencia. En el perfil interno existen 3 distintas matrices que almacenan contadores de ocurrencia de cada símbolo alfabético, costos de alineación y secuencias en la representación con espacios.

Los costos de los espacios se determinan de acuerdo a la función de penalización clásica afín. Se usan 4 distintos tipos de espacios: extensión de espacio terminal, espacio terminal abierto, espacio abierto y extensión de espacio.

AILYN APARICIO VILLANUEVA