DIALIGN-T: Un mejor algoritmo para el segmento basado en la alineación de secuencias múltiples

Los enfoques tradicionales para la alineación de secuencias múltiples son o mundial o métodos locales. Global métodos alinear secuencias desde el principio hasta el final [4, 24, 9]. Sobre la base de la Needleman-Wunsch función objetivo [18], estos algoritmos definir la puntuación de una alineación sumando las puntuaciones de cada uno de los pares y de residuos mediante la imposición de sanciones brecha, sino que tratar de encontrar una alineación con la máxima puntuación total, en el sentido de la presente definición . Por el contrario, la mayoría de los métodos locales de tratar de encontrar uno o varios conservadas motivos compartidos por todas las secuencias de la entrada [29, 12, 5].

Durante los últimos años, una serie de híbridos se han desarrollado métodos que combinan a nivel mundial y local las características de alineación [17, 19, 2, 8]. Uno de estos métodos es el segmento enfoque basado en la adaptación a múltiples [17], donde las alineaciones se componen de pairwise local secuencia similitudes. En total, estas similitudes podrá cubrir la totalidad de las secuencias de entrada - en cuyo caso, a nivel mundial se produce la alineación - pero también puede ser restringido a los locales si no hay motivos mundial homología es detectable. Por lo tanto, este enfoque puede regresar mundial o local alineaciones - o una combinación de ambos - dependiendo del grado de similitud entre las secuencias de entrada.

En lugar de comparar el único residuo de pares, la serie de sesiones de enfoque basado en toda la compara subseries de las secuencias de entrada a unos de otros. Los bloques de construcción básicos para pairwise y múltiples alineación son in-gapped pairwise local con dos alineaciones de las secuencias que se examina. Esos locales están llamados alineaciones alineaciones fragmento o fragmentos, que pueden tener cualquier longitud hasta una cierta longitud máxima M. Así, un fragmento f corresponde a un par de subseries de la igualdad de longitud de dos de las secuencias de entrada. En pareja o múltiples alineaciones se componen de tales fragmentos, el algoritmo construye un adecuado Una colección de fragmentos que es coherente en el sentido de que todos los fragmentos de A se puede representar al mismo tiempo en una salida de la alineación múltiple.

Tenga en cuenta que, desde múltiples alineaciones se componen de locales pairwise alineaciones, conserva motivos no están obligados a participar todos los de la entrada de las secuencias. A diferencia de nivel local para múltiples algoritmos de alineación, la serie de sesiones de enfoque, por lo tanto, es capaz de detectar homologías compartida por sólo dos de las secuencias alineadas. Con su capacidad para hacer frente a ambos, a nivel mundial y local relacionados con la secuencia fija y con su capacidad para detectar similitudes locales que participen sólo un subconjunto de las secuencias de entrada, la serie de sesiones de enfoque es mucho más flexibles que los métodos estándar para múltiples alineación. Se puede aplicar a la secuencia de las familias que no están alignable por los métodos estándar, que es la principal ventaja del segmento basado en la alineación frente al más tradicional de los algoritmos de alineación. La anterior aplicación de la serie de sesiones de base de múltiples alineación enfoque es DIALIGN 2,2 [16].

Durante los últimos años, estudios sistemáticos se han llevado a cabo real y artificial de los conjuntos de datos de referencia para evaluar la exactitud de la alineación de varios programas [26, 11, 20]. Estos estudios DIALIGN llegó a la conclusión de que es superior a otros programas si secuencia fija con homologlis locales se suman. En secuencias con homología débil, pero a nivel mundial, sin embargo, la anterior aplicación del programa es a menudo fuera realizado por métodos puramente mundial como CLUSTAL W [24], por medthods híbrido como T-CAFÉ [19] o [13] POA, o Por el recientemente desarrollado programas MÚSCULO [8] y PROBCONS [6] que son en la actualidad los métodos con mejores resultados a nivel mundial para múltiples proteínas alineación. En la siguiente sección, se muestra que la inferioridad de DIALIGN 2,2 débilmente, pero en el mundo relacionados con la secuencia fija se debe a la función objetivo que utiliza el programa. Si el programa puede elegir entre (a) un mundial pairwise alineación compuesta de muchos fragmentos de fragmentos individuales con bajos puntajes y (6) la adaptación local de una alternativa que consiste en sólo unos pocos fragmentos aislados con mayores puntuaciones individuales, se tiende a preferir el segundo tipo de Alineación más de la primera. En consecuencia, para las secuencias mundial, pero con una débil similitud, DIALIGN es vulnerable a espurios aleatorios similitudes.

En el presente trabajo se describe la reinstalación completa aplicación de la DIALIGN algoritmo que supera algunas de las deficiencias de la anterior versión del programa, 2,2. El documento se organiza de la siguiente manera: en la siguiente sección, se discute la función objetivo que DIALIGN utiliza para evaluar la calidad de los diferentes alineamientos para un determinado conjunto de datos de entrada. Nos muestran que esta función objetivo sistemáticamente a lo largo de las estimaciones locales aisladas de alineaciones en comparación con otras alineaciones que se prolongará durante toda la duración de las secuencias. A continuación, presentamos dos heurística para pairwise múltiples y alineación, respectivamente, para contrarrestar esta tendencia de equilibrio hacia aislados local similitudes. A continuación describimos las características adicionales de nuestra nueva aplicación, y en en la sección de resultados y discusión, evaluamos nuestra herramienta de software y la comparamos con la anterior y la aplicación de DIALIGN a otra norma de alineación de varios programas.

Desde un ordenador del científico punto de vista, la alineación de secuencias es un problema de optimización. La mayoría de los algoritmos de alineación son - explícita o implícitamente - sobre la base de una función objetivo, es decir, de algún tipo de calificación de la asignación de un régimen de nivel de calidad a todo lo posible alineación de una determinada secuencia de entrada establecidos. Sobre la base de ese esquema de puntuación, los diferentes algoritmos de optimización se usan para encontrar óptima o casi óptima alineaciones. Por múltiples alineación, una variedad de técnicas de optimización que se han propuesto. Estos algoritmos difieren sustancialmente de unos a otros en vista de su complejidad computacional, y en vista de su capacidad de encontrar o aproximar numéricamente óptima alineaciones. Sin embargo, la característica más importante de un programa de adaptación no es el algoritmo de optimización que utiliza, sino más bien el objetivo subyacente función que se utiliza para la producción de alineaciones puntuación posible. Si la función objetivo es biológicamente erróneo mediante la asignación de puntajes altos para biológicamente alineaciones de sentido, entonces incluso los más eficientes algoritmos de optimización sólo son eficaces en lo que matemáticamente alta puntuación tontería alineaciones. Con una función objetivo más realista, sin embargo, incluso ingenuos heurística puede llevar a biológicamente posible alineaciones.

La función objetivo que usamos en la serie de sesiones de enfoque se define como sigue: cada una de las posibles fragmento (segmento par) f se le asigna una puntuación de peso w (f), en función de la probabilidad de P (f), de ocurrencia aleatoria de tal fragmento. Más precisamente, el programa utiliza una función de la similitud s de asignar un puntaje s (a, b) a cada uno de los pares posibles (a, b) de los residuos. Para la alineación de proteínas, uno de los habituales de sustitución de las matrices se pueden utilizar; para la alineación de secuencias de ADN o ARN, el programa simplemente distingues entre partidos y la falta de adaptación. Por un fragmento f, su Needleman-Wunsch Resultado NW [f] se calcula que se define como la suma de los valores de similitud alineados nucleótidos o aminoácidos (nota de nuevo, que no contienen fragmentos de las lagunas). Para definir la puntuación de peso w (f) de f, consideramos que la probabilidad de P (f), de encontrar un fragmento f 'de la misma longitud que f y con una puntuación de Needleman-Wunsch NW [f'] ≥ NW [f], en Aleatoria de las secuencias de la misma longitud que la entrada de las secuencias. W (f) se define como el logaritmo negativo de esta probabilidad, ver [14] para más detalles. La puntuación total de un - pairwise o múltiples - alineación se define como la suma de las puntuaciones de peso de los fragmentos que se compone de los huecos no son penalizados. La idea es menos probable que el fragmento de una determinada colección es que se produzca sólo por azar, la más probable es que se biológicamente relevantes por lo que el mayor debe ser su puntuación. Así, mientras que los enfoques estándar alineación tratar de encontrar una alineación más probable es que en el supuesto de que la entrada de las secuencias están relacionados por ascendencia común [7], se intenta encontrar una alineación más probable es que en el supuesto de que las secuencias no están relacionados . Un pairwise alineación en el sentido de la definición anterior corresponde a una cadena de fragmentos, y una alineación con la máxima puntuación de peso total puede encontrarse utilizando un fragmento de recursivo el procedimiento [15]; para múltiples alineación, un codicioso heurística se utiliza [1 , 14].

Como se explicó anteriormente, la puntuación DIALIGN define S (A), de una alineación A = (f ₁ ,..., _k) f como la suma de las puntuaciones de peso w (f _i), de sus fragmentos, y estos resultados son de peso, A su vez, que se define como negativo logaritmos de las probabilidades P (f _i), de su ocurrencia aleatoria. Así, la puntuación de S (A) se calcula como

Y la búsqueda de un alineamiento con la máxima puntuación es equivalente a la búsqueda de una colección de fragmentos de A = f ₍₁ ,..., _k) f producto con un mínimo de probabilidades Π _{f ∈ P} (f). Pero teniendo en cuenta el producto de los fragmentos de probabilidades medios a considerar la probabilidad de su aparición conjunta en el supuesto de que estos eventos son independientes uno de otro. Esto sería razonable si queremos buscar una arbitraria colección de fragmentos con baja probabilidad de ocurrencia aleatoria. En nuestro enfoque, sin embargo, es necesaria la recolección de un fragmento de ser coherente, de modo que el conjunto de combinaciones de fragmentos permitido es reducido drásticamente. La probabilidad de encontrar un conjunto coherente de los fragmentos, en consecuencia, mucho más pequeños que el producto de las probabilidades de encontrar todos los fragmentos individuales correspondientes. De este modo, al utilizar el producto Π _{f ∈ P} (f), DIALIGN general, el exceso de las estimaciones de la probabilidad P (A), de azar se produzca un alineamiento A.

En nuestro contexto, el punto crucial es que las probabilidades P (A) - y, por tanto, las puntuaciones S (A) - no son uniformemente sobre-estima - o subestimada, respectivamente - para todas las posibles alineaciones, pero no hay gran diferencia entre Globales y locales alineaciones. Para una alineación Un _g mundial que abarca la mayoría de las secuencias, la discrepancia entre la probabilidad real P (A _g) de su ocurrencia aleatoria y la aproximación P (f) utilizados por DIALIGN es mucho más importante que para un local de la alineación A _l. Esto se debe a que a nivel mundial la adaptación corresponde a una densa colección de fragmentos, así que aquí la coherencia limitaciones son mucho más estrictas que en un local de alineación que consiste en sólo unos pocos fragmentos aislados. Como resultado de ello, DIALIGN relativamente más de las estimaciones de la probabilidad P (A _g) de un mundial aligment A _g en comparación con una alternativa local alineación A _l, por lo que en virtud de las estimaciones de la puntuación de S (A _g) en comparación con la puntuación de S (A L).

En la sección anterior, hemos explicado por qué la función objetivo utilizada en DIALIGN sistemáticamente prefiere local alineaciones más alternativa global alineaciones de la misma serie de datos. La mejora de la función objetivo que se use una mejor aproximación a la probabilidad P (A), de azar se produzca un alineamiento Un tendrían que tener en cuenta las limitaciones combinatoria dada por nuestra condición de la coherencia. La definición de esa función objetivo sería matemáticamente difícil. Para nuestro nuevo programa, por lo tanto, utilizar la función objetivo que se ha utilizado en versiones anteriores de DIALIGN. Sin embargo, introducir dos heurística para contrarrestar los prejuicios en función de este objetivo hacia aislados local alineaciones.

La alineación pairwise algoritmo que estamos utilizando es una modificación del espacio-eficiente fragmento de encadenar algoritmo se describe en [15]. En cada posición (i, j) en la matriz de comparación, este algoritmo considera que todos los fragmentos (= segmento pares) a partir de (i, j) hasta una cierta longitud máxima M. Por proteína alineación, el programa anterior DIALIGN 2.2 utiliza un valor por defecto de M = 40; H puede reducirse a acelerar el programa, pero esto puede resultar en la disminución de la calidad de la alineación. Inicialmente, la limitación de la longitud de los fragmentos se ha introducido para reducir el tiempo de funcionamiento del programa; esta manera, el tiempo de la complejidad pairwise fragmento de encadenar algoritmo se reduce de O (l ³⁾ O (l ^2), donde l es la longitud máxima de Las dos secuencias. Uno podría pensar que el aumento de la máxima longitud de los fragmentos de M se traduciría en la mejora de la calidad de la alineación. De hecho, se observó que, con leve aumento de los valores de M, se obtuvieron mejores alineaciones, pero con valores de M> 50, la calidad de los alineamientos producidos disminuido drásticamente.

En sistemática pruebas, se observó que para los grandes valores de M, salida alineaciones menudo contienen fragmentos largo de una mezcla de alta y baja puntuación de puntuación sub-fragmentos. Con un ideal función objetivo, un solo largo fragmento que contiene f baja puntuación sub-fragmentos automáticamente recibe una puntuación inferior a la cadena de breves fragmentos que se obtendría de f mediante la eliminación de los bajos de puntuación sub-fragmentos. Como resultado, la producción alineaciones tienden a consistir en fragmentos más cortos y no más largo de los fragmentos con baja puntuación sub-regiones. Por las razones expuestas en la sección anterior, sin embargo, el sistema de puntuación utilizado por DIALIGN exceso de las estimaciones de largo solo fragmentos en comparación con las cadenas de pequeños fragmentos que se obtendría mediante la eliminación de las regiones de baja puntuación largo de los fragmentos.

En nuestro nuevo enfoque, la utilización de los siguientes heurística para evitar que el algoritmo de selección de los fragmentos de largo con baja puntuación sub-regiones. Definimos una longitud L umbral de baja calidad sub-fragmentos. Sub-longitud de los fragmentos de negativos con L ≥ Needleman-Wunsch Resultado se permiten dentro de breves fragmentos, pero se excluyen en fragmentos de longitud ≥ T donde T <M es un parámetro que se puede ajustar el usuario bu. Por un par de secuencias de entrada S ₁ y S _2, y habida cuenta de valores para los parámetros T, M y L, nuestro nuevo algoritmo procede de la siguiente manera. Let f (i, j, k) designar el fragmento de longitud k que comienza en la posición i en la secuencia S ₁ y en la posición j en la secuencia S _2, respectivamente. Por S ₁ [k], denotamos el k-ésimo carácter en la secuencia S _i. Como en el original DIALIGN algoritmo, que atravesamos la comparación de la matriz S ₁ y S _2, y en cada posición (i, j), consideramos que a partir de los fragmentos de esta posición; adecuados fragmentos se añade a un conjunto creciente de candidatos fragmentos F De la que el algoritmo selecciona un fragmento de la cadena con la máxima puntuación total con respecto a la función objetivo [15]. Si una región de baja calidad se produce, la máxima longitud de los fragmentos de M (i, j) de los fragmentos a partir de (i, j) se reduce de H para T. Más formalmente, que lleve a cabo los siguientes pasos a partir de fragmentos de una posición fija (i, j):

1. Inicialmente, la duración máxima de los fragmentos a partir de (i, j) es M (i, j) = M.

2. Comenzamos con longitud k = 1, es decir, consideramos que el fragmento f (i, j, 1).

3. Si el actual es superior a la longitud de los fragmentos k M (i, j) entonces el procedimiento se detiene y seguimos con fragmentos a partir de (i, j + 1).

4. Si la puntuación de similitud s (S ₁ [i + k - 1], S ₂ [j + k - 1]) de los últimos residuos de par en f (i, j, k) no es negativo, tomamos el fragmento f ( I, j, k) en cuenta si lo agrega a la serie F, y continúe con el paso 7. De lo detectó el potencial comienzo de una baja calidad sub-fragmento a partir de las posiciones i + k - j + 1 y k - 1, respectivamente.

5. En este caso, hacer un predictiva y calcular el NW-Resultado de la posible baja de calificación fragmento f (i + k - 1, j + k - 1, L), que se define como

6. Si NW [f (i + k - 1, j + k - 1, L)] <0, que realmente detectó una baja calidad sub-fragmento. Si k> T, el procedimiento se detiene y no aumentar más de k se está considerando, de lo establecido M (i, j) = T.

7. La longitud k se incrementa en 1 y continuamos con el paso 3.

Por defecto, el programa utiliza un umbral de longitud de baja calidad sub-fragmentos de L = 4 y la longitud máxima de los fragmentos que contienen estas regiones de baja calidad es T = 40. Estos valores se han calculado en base a la sistemática de pruebas se ejecuta en BAliBASE. En este punto, queremos mencionar el impacto de los parámetros L y T en la calidad de la producción producidos alineaciones. Por ejemplo, con valores de L = 3 L = 5 o de la alineación de la calidad es empeorado dramáticamente en comparación con el valor por defecto L = 4.

Nuestro criterio para detener la baja de puntuación sub-fragmentos no sólo mejora la calidad de las alineaciones, pero lo que también reduce el tiempo de funcionamiento del programa. El tiempo de ejecución de nuestro pairwise algoritmo es proporcional al número de fragmentos que se consideran para la alineación. Así, el peor de los casos el tiempo es la complejidad de O (l ₁ l ₂ M), donde l ₁ y l ₂ son las longitudes de las secuencias de entrada. Al excluir a largo fragmentos con baja puntuación sub-fragmentos, pasamos por alto un gran número de fragmentos que se han considerado para la alineación en las versiones anteriores del programa. Por lo tanto, nuestra nueva heurística nos permite incrementar el máximo posible la longitud de los fragmentos de 40 a M = H = 100, sin aumentar excesivamente el número total de fragmentos que se han de examinarse. Una ampliación de la M está prohibida debido a la inestabilidad numérica. En total, las alineaciones resultantes pueden reflejar la ampliación de las actuales homologías más realista que la versión anterior de DIALIGN con sólo un aumento moderado en el programa de tiempo de funcionamiento.

Como se mencionó anteriormente, DIALIGN codiciosos optimización utiliza un procedimiento de múltiples alineación. El orden en el que se incluyen fragmentos múltiples en la alineación se determina en base a su peso resultados. Un problema con este enfoque es que los codiciosos si un fragmento es mal aceptada por múltiples alineación, que no se puede eliminar más adelante. Tenga en cuenta que ni siquiera una sola decisión equivocada en el codicioso procedimiento puede afectar a la calidad resultante de la alineación de forma espectacular. Por lo tanto, especial cuidado hay que tener para dar prioridad a los fragmentos de los codiciosos algoritmo. Hemos observado que en muchos casos falsa, pero de alta puntuación fragmentos de pairwise alineaciones son incompatibles con una buena alineación general múltiples. Debido a su peso resultados, sin embargo, estos fragmentos pueden ser incorporados a la alineación de las múltiples DIALIGN original, lo que llevaría a la salida de las alineaciones de menor calidad.

Como se explica en la sección anterior, el peso de la puntuación de un fragmento depende de la probabilidad de su ocurrencia aleatoria de las secuencias en la longitud de la secuencia de entrada. Así, el peso resultados son puramente basado en las propiedades intrínsecas de fragmentos - y de la duración de las secuencias de entrada -, pero que no toman en cuenta el contexto de un fragmento pairwise dentro de la alineación. En realidad, sin embargo, el contexto de un fragmento es fundamental para evaluar su fiabilidad. Si un fragmento f es parte de una alta puntuación pairwise alineación, entonces f es, por supuesto, mucho más probabilidades de ser biológicamente significativo que si el mismo fragmento f se encuentra aislado en un otra relacionada con secuencias. Por lo tanto, la similitud general entre dos secuencias hay que tener en cuenta si los fragmentos se ordenan antes de la codiciosos procedimiento.

En nuestro nuevo programa, se adopte el siguiente enfoque: multiplicamos el peso de la puntuación de cada fragmento de la plaza del peso total de la puntuación de la secuencia de pares respectivos dividido por el peso total de la puntuación de todos los pairwise alineaciones. Let S ₁ ,..., S _n ser las secuencias de entrada y dejar que sea f un fragmento de las secuencias de S _i y S _j. A continuación, dejar w (S _i, S _j) denotan el peso total de la puntuación pairwise alineación de S _i y S _- es decir, la suma de las puntuaciones de un peso óptimo de la cadena de fragmentos - y deje W ser la suma total de las puntuaciones de peso De todos pairwise alineaciones. Es decir, definimos

A continuación, definir el peso ajustado Resultado

Y en nuestro algoritmo de codiciosos, los fragmentos se ordenan en función de sus resultados ajustados w '(f). De esta manera, preferimos fragmentos pertenecientes a la secuencia de pares de alta similitud de los más débilmente relacionados con la secuencia de pares. En total, el peso de este ajuste respeta la similitud de la secuencia de pares mejor que el método anterior y, por lo tanto, puede mantener los codiciosos procedimiento de la adición de fragmentos aislados espurios que se han llevado a una menor puntuación y biológicamente menos significativa salida de la alineación. La lista ordenada de fragmentos de la óptima pairwise alineaciones se mantienen en un montón estructura binaria que se pueda actualizar de manera eficiente cuando los fragmentos son incompatibles para ser eliminados o modificados, como se explica en la siguiente sección.

En el planteamiento original DIALIGN, un fragmento f es incompatible descartarse completamente en el procedimiento codicioso - incluso si sólo algunos pares de residuos son incompatibles con la actual alineación. En esa situación, sería por supuesto más razonable de eliminar sólo los residuos incompatibles pares de f y dar a los restantes sub-fragmentos de una segunda oportunidad en el proceso de selección codiciosos. Es fácil ver que un fragmento f es compatible con un alineamiento existente A si y sólo si cada par de residuos alineados en f es coherente con una. En nuestra nueva aplicación, se utiliza el siguiente procedimiento para la no-coherente fragmentos. Un fragmento incompatible f se procesa de izquierda a derecha. A partir de la izquierda de la mayoría de residuos par, eliminar todos los residuos incompatibles pares hasta que nos encontramos con el primer par coherente p. A continuación, tenemos en cuenta todos los pares a partir de residuos compatibles con p hasta que encontramos de nuevo una pareja de residuos incompatibles. De esta manera, obtenemos un sub-fragmento f 'de f para el que debemos calcular la puntuación de peso w (f'). De la construcción, f 'es coherente con la actual alineación, y podría, en principio, se añadirá a la lista de los fragmentos.

Sin embargo, no incluirá de inmediato f 'en la creciente múltiples alineación desde la puntuación w (f') podría ser más pequeña que la partitura original w (f). En lugar de ello, insertar f ', en la posición adecuada en nuestra lista de los fragmentos ordenados en función de su peso ajustado Resultado w' (f '). Con la estructura binaria heap descritos en la sección anterior, de conformidad sub-fragmentos incoherentes de los fragmentos se puede volver a colocar de manera eficiente en función de su recién calculado pesos ajustados. El resto de f es tratada en consecuencia, es decir, incompatibles pares de residuos se eliminan y los restantes sub-compatible fragmentos se insertan en las posiciones adecuadas en la lista de candidatos fragmentos. Tenga en cuenta que con nuestra función de ponderación w, el peso Resultado w (f '), de un sub-fragmento f' que figura en un fragmento f, en general, puede ser mayor que el peso w (f). En la situación anterior, sin embargo, tenemos necesariamente w (f ') ≤ w (f') [y, por tanto, w '(f') ≤ w '(f)], ya que supone que f es parte de la óptima adaptación de la pairwise Dos secuencias. Si la puntuación w (f '), de un sub-fragmento de f superado w (f), entonces f' que se han seleccionado para la alineación óptima pairwise en lugar de f.

La anterior aplicación DIALIGN 2,2 utiliza antes de la probabilidad calculada tablas para calcular el peso fragmento resultados; estos cuadros se basan en la sustitución de la matriz BLOSUM 62. Ellos se han calculado años atrás y son difíciles de volver a calcular si un usuario desea emplear otra similitud matriz. Por tanto, no es posible ejecutar DIALIGN 2,2 sustitución con distintas matrices BLOSUM 62. En nuestra nueva aplicación, usamos bastante eficaz para estimar las probabilidades de que se utilizan para el cálculo de puntuación de nuestro peso. Hemos calculado la validez de las tablas de probabilidad para una variedad de matrices de sustitución. Además, el usuario puede volver a calcular estos cuadros' sobre la marcha 'arbitraria de matrices con un moderado aumento de la duración del programa.

Como se explica en la sección Objetivo funciones para la alineación de secuencias, definimos el peso de la puntuación de un fragmento de secuencias S f _i y _j como S

W (f) = - logP (f)

Donde P (f) denota la probabilidad de la ocurrencia de un fragmento f 'de la misma longitud que f y con Needleman-Wunsch Resultado NW [f'] ≥ NW [f] en secuencias aleatorias de la misma longitud que S _i y S _j. Por azar nos referimos a secuencias independientes idénticamente distribuidas (iid) secuencias donde cada residuo se produce en cualquier posición con probabilidad de 1 / 4 de secuencias de ácidos nucleicos y 1 / 20 para las secuencias de la proteína, respectivamente. En la siguiente, se describe la forma en que nuestro programa se aproxima a la probabilidad de P (f).

En una primera etapa, se calcula la probabilidad De encontrar un fragmento f 'de longitud n y con Needleman-Wunsch Resultado NW [f'] ≥ s en secuencias aleatorias de longitud 2 n. Tenga en cuenta que Depende de la matriz subyacente de sustitución, pero no sobre la duración o la composición de las secuencias de entrada de S _i y S _j. Los valores numéricos Se estiman de la siguiente manera:

1. Random experimentos se llevan a cabo para obtener una estimación preliminar Para . Los valores experimentales Debe aproximar Con la suficiente precisión para los valores de n y s que suficientes datos experimentales están disponibles en condiciones. Este es el caso si No es demasiado pequeño.

2. Para los pequeños valores de la , En primer lugar, calcular la probabilitys P ₁ (s, n) para un solo fragmento aleatoria f 'de longitud n para tener un Needleman-Wunsch Resultado NW [f'] s ≥. P ₁ (s, n) puede ser fácilmente calculada como Una suma de convolución productos. Similares como en [14], los pequeños valores de la Se calcula mediante la fórmula de aproximación

3. En definitiva, definimos Para un determinado valor s de examinar por primera vez el trivial caso n = 1 y, a continuación, la definición de n = 2 ,..., M:

El procedimiento descrito para estimar Es computacionalmente exigente. Como los valores No dependen de la secuencia de entrada, nos pre-calculado las probabilidades de varios estándar de sustitución de las matrices y sus valores almacenados en archivos auxiliares, de donde se recuperan durante el programa plazo.

En un segundo paso, usamos Para estimar la probabilidad de P (s, n) para encontrar un fragmento f 'de longitud n con Needleman-Wunsch Resultado NW [f'] ≥ s en secuencias de la longitud de la secuencia de entrada. Este paso es computacionalmente menos costoso y, por consiguiente, pueden llevar a cabo durante el programa ejecutado. Deje que l l _i y _j se las longitudes de las secuencias de entrada Si y S _j, respectivamente. Similares como en [14], calcular P (s, n)

Donde P _T es un parámetro umbral. Durante un programa de plazo, los valores de P (s, n) se calculan para todos los posibles valores de n y s pairwise antes de la alineación de secuencias S S _i y _j se lleve a cabo. La negativa logaritmos-log P (s, n) se almacenan en una mirada de la tabla donde son recuperados durante la pairwise para definir la alineación de los fragmentos de partituras.

Estamos pre-calculado las probabilidades Para la sustitución de varias de las matrices BLOSUM familia. Para determinar los valores de probabilidad experimental P _exp (s, n), llevamos a cabo 10 ⁶ experimentos aleatorios para cada par de parámetros (s, n). En este sentido, hemos considerado los valores de n entre 1 y un máximo de longitud de los fragmentos de M = 100. Los archivos con los resultados de los valores Valores se distribuyen junto con nuestro paquete de software. Para calcular P (f), se utiliza un umbral de probabilidad de P _T = 10 ^-8. Nuestro programa también puede ser utilizado para calcular los valores Para arbitraria definida por el usuario la sustitución de las matrices. El cálculo de estos valores utilizando 10 ⁵ experimentos aleatorios para cada valor de n y s tarda unos 20 minutos en una estación de trabajo Linux (RedHat 8.0) con un 1,5 Ghz procesador Pentium 4 y 512 MB Ram. En nuestra experiencia, 10 ⁵ experimentos aleatorios son suficientes para obtener alta calidad las estimaciones de probabilidad.

Se evaluó el desempeño de nuestro programa y en comparación a la alineación alternativa multi-herramientas de software utilizando una amplia variedad de secuencias de referencia. Como un primer conjunto de datos de referencia, hemos utilizado la conocida BAliBASE 2,1 [25]. BAliBASE se ha utilizado en numerosos estudios para probar la exactitud de múltiples proteínas alineación software. Cabe mencionar que, aunque algunas de las secuencias de referencia en BAliBASE contienen las inserciones y deleciones de tamaño moderado, BAliBASE está fuertemente sesgado en favor de las familias de proteínas relacionadas con el mundo. Todos BAliBASE contienen secuencias homólogas con bloques básicos verificado estructura 3D; alineación de los programas son evaluados de acuerdo a su capacidad para alinear correctamente estos bloques. Según el BAliBASE autores, estos bloques básicos cubrir el 58% de los residuos en la base de datos. Sin embargo, es evidente la similitud de secuencia no se limita a esas regiones de la estructura a fin de verificar 3D, en realidad, mucho más que el 58% de la longitud total de secuencias son homólogas a otras secuencias en la secuencia respectivas familias. Además, las secuencias en BAliBASE no son realistas secuencias de longitud completa, pero se han truncado por la BAliBASE desarrolladores, a fin de eliminar no relacionados con las partes de las secuencias. Como resultado de ello, BAliBASE casi en su integridad a nivel mundial relacionados con la secuencia fija; esta es la razón por la alineación de los programas mundiales, como CLUSTAL W realizar mejor sobre estos datos de referencia.

Para estudiar el desempeño de los programas de adaptación a nivel local relacionados con la secuencia fija, Lassmann y Sonnhammer aleatoria secuencias artificiales utilizados con motivos implantados conservadas [11]. Random secuencias se utilizan con frecuencia para evaluar los instrumentos de análisis computacional de secuencias, que son particularmente útiles para estudiar la especificidad de un instrumento, ver por ejemplo [23, 10, 20]. Lamentablemente, el punto de referencia de datos por Lassmann y Sonnhammer no están a disposición del público. Por lo tanto, creamos nuestra propia base de datos de referencia para la adaptación local de múltiples proteínas que hemos denominado IRMBASE (Implantados Rose motivos Base).

Lassmann y Sonnhammer Como hizo en su anterior estudio, elaborado artificial de los grupos de secuencias conservadas motivos ROSE utilizando la herramienta de software [23]. ROSE simula el proceso de evolución molecular. Un conjunto de "filogenéticamente" relacionados con las secuencias es creado a partir de una definida por el usuario 'antepasado' secuencia de acuerdo a un árbol filogenético. Durante este proceso de secuencia de caracteres al azar se inserta, suprimido y sustituido el marco de un pre-definidos modelo estocástico. De esta manera, una secuencia conocida de la familia 'evolución' se obtiene, por lo que el "correcto" múltiples alineación de estas secuencias se conoce. Tenga en cuenta que estos desajustes alineaciones contienen, así como las lagunas. Hemos insertado familias de los motivos creados por conservadas en ROSE escogido de forma aleatoria en posiciones no relacionadas con las secuencias aleatorias. De esta forma, también produjo tres conjuntos de referencia ref1, ref2 y ref3, de secuencias de proteínas artificiales. Ref1 secuencias de contener uno de cada motivo y secuencias de ref2 y ref3 contienen dos y tres motivos cada uno, respectivamente. Cada conjunto de referencia se compone de 60 familias secuencia, el 30 de los cuales contienen ROSE motivos de longitud mientras que los 30 restantes 30 familias de los motivos de longitud 60. Secuencia de 20 familias en cada uno de los conjuntos de referencia consta de 4 secuencias de cada uno, otras 20 familias constará de 8 secuencias mientras que el restante 20 familias constará de 16 secuencias. En ref1, aleatoria de las secuencias de longitud 400 se añaden a la conserva ROSE motivo mientras que para ref2 y ref3, seqences aleatoria de longitud se añaden 500.

Por tanto BAliBASE y IRMBASE, hemos utilizado dos criterios diferentes para evaluar la adaptación de múltiples herramientas de software. Se utilizó la suma de la puntuación de pareja donde el porcentaje de pares alineados correctamente de los residuos se toma como medida de calidad de las alineaciones. Además, utilizamos la columna Resultado donde el porcentaje de columnas en una correcta alineación es el criterio de calidad de la alineación. Ambos esquemas de calificación se limita a los bloques básicos de referencia dentro de las secuencias en que la 'verdad' que se conoce la alineación. Por IRMBASE, el núcleo de los bloques se definen como las conservadas ROSE motivos. En general, la suma de la puntuación de pares es más apropiada que la columna de puntuación, porque hace caso omiso de esta última puntuación de todos los residuos correctamente alineados en una alineación de la columna, si una sola de residuos en esta columna está mal alineada. Sin embargo, hay situaciones en las que la puntuación de la columna es más significativo que la suma de la puntuación de pares. Este es el caso, por ejemplo, para BAliBASE de referencia establece que contienen 'huérfano secuencias ".

Para comparar los resultados de diferentes programas a las respectivas alineaciones de referencia, hemos utilizado C. Notredame 's aln_compare programa [19]. Los cuadros 1 y 2 resumen el rendimiento de DIALIGN-T, DIALIGN 2,2, CLUSTAL W, MUSCLE, PROBCONS, T-CAFÉ y POA IRMBASE mientras que en los cuadros 3 y 4 muestran BAliBASE sobre su exactitud. Además, en los cuadros 5, 6, 7 y 8 contienen el porcentaje de secuencia fija que DIALIGN-T es un rendimiento superior de los otros programas que hemos probado. Los cuadros 1 y 2 indican que, a nivel local relacionados con la secuencia de las familias, DIALIGN-T es significativamente superior a los algoritmos DIALIGN 2,2, T-CAFE, MUSCLE, POA y CLUSTAL W. Sólo DIALIGN-T, DIALIGN 2,2, y T-CAFÉ (en Un muy reducido manera) PROBCONS producido resultados razonables en IRMBASE 1,0. Sin embargo, DIALIGN-T es la forma más rápida y precisa entre todos los métodos que hemos examinado. Nos gustaría hacer hincapié en que el desempeño de varios métodos de alineación de datos simulados aproximadamente sólo refleja su rendimiento en datos reales. No obstante, en ausencia del mundo real datos de referencia para múltiples locales alineación, los resultados sobre IRMBASE nos puede dar una idea de cómo tratar con diferentes algoritmos local conserva motivos.

Para secuencias relacionadas con el mundo las familias, los cuadros 3 y 4 muestran que, en promedio, supera a DIALIGN-T DIALIGN 2,2 y 2,1 POA sobre BAliBASE mientras que su rendimiento es similar a CLUSTAL W. Por el contrario, la versión anterior DIALIGN 2,2 es claramente un rendimiento superior por CLUSTAL W En estos conjuntos de datos. Por último, DIALIGN-T es todavía un rendimiento superior a muchas de las secuencias de prueba BAliBASE por T-CAFÉ, y MÚSCULO PROBCONS; este último programa es actualmente el mejor desempeño de múltiples aligner sobre BAliBASE. La superioridad de nuestro nuevo enfoque en comparación con el 2,2 y DIALIGN POA es claramente estadísticamente significativas según el Test de Wilcoxon Firmado Rank Test. El BAliBASE referencia establece ref1, ref2 y ref3 donde las secuencias contienen sólo pequeñas inserciones y deleciones, el desempeño de DIALIGN-T es más o menos comparable a CLUSTAL W, pero aún sigue siendo significativamente peor que la T-CAFÉ, PROBCONS o MÚSCULO. Nuestro programa es estadísticamente significativamente superior o igual a todos los métodos, excepto MÚSCULO PROBCONS y, en la secuencia fija con grandes inserciones o deleciones (ref4 y ref5 de BAliBASE).

En general, el rendimiento relativo de las diferentes herramientas de alineación es similar en virtud de las dos alternativas de los criterios de evaluación que hemos utilizado (suma de los pares y la columna Resultado) - aunque, los valores absolutos de la columna de resultados son, por supuesto, inferior a la suma de - Pares de puntuaciones. Tal vez sorprendentemente, ambas versiones de DIALIGN son superiores a todos los demás programas en nuestro estudio en el nivel local relacionadas con secuencias de IRMBASE - mientras que por otro lado, se superaron a DIALIGN por métodos alternativos de conjuntos de referencia 4 y 5 de BAliBASE. Estos conjuntos de la secuencia también se consideran relacionados con el nivel local debido a que contienen más grandes inserciones y deleciones entonces BAliBASE otras secuencias. La razón de esta aparente discrepancia es que el ref4 y ref5 secuencia fija en BAliBASE no están realmente relacionados con el nivel local, pero aún muestran alguna similitud fuera de los principales bloques conservados. En IRMBASE, por el contrario, la secuencia de similitud se limita estrictamente a los motivos conservados.

Desde que volvió a aplicarse el DIALIGN algoritmo de la nada y utiliza una variedad de nuevas funciones del programa, no es posible saber con exactitud hasta qué punto cada uno de estos elementos contribuyeron a la mejora de los resultados del programa. Sistemática de pruebas con distintos parámetros indican, sin embargo, que la superioridad de nuestro nuevo programa en comparación con el programa anterior DIALGIN 2,2 en tanto localmente como en la secuencia de las familias relacionadas globaly se debe principalmente a las funciones del programa se explica en la tercera sección. La mejora que hemos logrado con estas heurística es estadísticamente significativa. Las características se explica en la sección Otras funciones del programa mejorado también el programa exactitud, aunque aquí la mejora no fue estadísticamente significativa.

El cuadro 9 muestra el tiempo de funcionamiento del programa para los siete programas que hemos probado en nuestro estudio. DIALIGN-T es de alrededor de un 6% más lento que la anterior aplicación DIALIGN 2,2 sobre BAliBASE 2,1, pero en IRMBASE, DIALIGN-T es aproximadamente 30% más rápido que DIALIGN 2,2. En DIALIGN, el tiempo de CPU para múltiples alineación está principalmente dedicado a pairwise alineaciones que se realizan antes de los fragmentos se incluyen en la alineación múltiple. Como se explica en la sección Excluyendo baja puntuación sub-fragmentos, el tiempo de ejecución de pairwise alineación es aproximadamente proporcional al número de fragmentos que se consideran para la adaptación y, por secuencias de longitud l ₁ y l ₂ y un máximo de longitud de los fragmentos de M, hasta L ₁ l × ₂ × M fragmentos de ser examinados. En nuestro nuevo programa DIALIGN-T, la mayor longitud de los fragmentos de M se incrementa a 100 en comparación con 40 para el programa original DIALIGN. No obstante, el programa de tiempo de funcionamiento es sólo ligeramente para el aumento de las proteínas relacionadas con el mundo de las familias y BAliBASE disminuido considerablemente para el local secuencias conservadas de IRMBASE. Esto se debe al criterio heurístico para detener los fragmentos introducido anteriormente. El más lento en nuestro programa de comparación se CAFÉ T-que es más de once veces más lento que DIALIGN-T sobre IRMBASE y más de cinco veces más lento en BAliBASE. POA es el método más rápido. El BAliBASE, el programa PROBCONS produce los mejores resultados en términos de precisión de alineación. El programa es, sin embargo, el segundo más lento después del programa T-CAFÉ en ambos BAliBASE y IRMBASE. MÚSCULO dispone hasta el momento el mejor compromiso entre tiempo de funcionamiento y calidad en el mundo relacionados con la secuencia de las familias, pero cuando se trata de locales alineaciones tanto tiempo de funcionamiento y reducir drásticamente la calidad de la alineación. El consumo de memoria de la aplicación de este método se ha mejorado en comparación con DIALIGN 2,2.

Con el desarrollo de DIALIGN-T, que mejoró significativamente el segmento basada en un enfoque de múltiples proteínas en la adaptación tanto a nivel local como a nivel mundial datos de referencia. La nueva heurística que nos presenta, en general, coherente favor de los grupos de bajos puntuación más fragmentos aislados fragmentos de mayor puntuación. De esta manera, mejoramos el rendimiento de los programas en el mundo relacionados con la secuencia que establece la serie de sesiones de enfoque anteriormente fue inferior a programas como CLUSTAL W y POA. En estos conjuntos de datos, nuestro nuevo método es mucho más exacto, pero sólo ligeramente más lento que DIALIGN 2,2. El BAliBASE, el desempeño de nuestro enfoque es ahora comparable a la popularidad mundial de la adaptación del programa CLUSTAL W. Para las familias de proteínas relacionadas con el nivel local, DIALIGN-T funciona claramente mejor y es también considerablemente más rápido que el anterior DIALIGN 2,2 que fue, hasta el momento, el mejor Disponibles a nivel local relacionadas con el método de las familias de proteínas. Además de estas mejoras, ahora es posible el uso arbitrario definido por el usuario, la sustitución de las matrices que no es posible que el programa original DIALIGN. Para mejorar aún más el desempeño de nuestro método, estamos pensando en mejorar los codiciosos DIALIGN algoritmo que utiliza para múltiples alineación. En lugar de centrarse en pairwise fragmento alineaciones, que se desarrollará heurística que son capaces de integrar múltiples locales alineaciones en la final de alineación múltiples. Este enfoque debería mejorar aún más la sensibilidad de nuestros métodos para el local conserva motivos.

Por último, nos gustaría hacer algunas observaciones generales sobre el ajuste de parámetros y evaluación del programa en la alineación de secuencias múltiples. Como ya se ha mencionado, hemos identificado los valores adecuados para nuestros parámetros T y L sobre la base de pruebas con BAliBASE, y suponemos que esta es la forma en que el programa para la mayoría de parámetros múltiples proteínas aligners se han afinado en los últimos años. Por lo tanto, la cuestión se ha planteado si la alineación actual de la proteína programas son overfitted con respecto a BAliBASE. Parámetro overfitting es un problema serio para muchos algoritmos de Bioinformática. Por ejemplo, muchos programas de predicción de genes con un gran número de parámetros a ajustar, de manera que es fácil de sintonizar estos programas para tener buenos resultados en un conjunto dado de datos de formación. Para este tipo de programas por lo que es absolutamente necesario separar claramente la formación de datos que se utilizan para el parámetro de ajuste de los datos de las pruebas que se utilizan para evaluar el programa. La situación es totalmente diferente en la alineación múltiple. La mayoría tienen múltiples aligners sólo un número muy reducido de parámetros a ajustar. Para nuestro algoritmo, por ejemplo, el único importante son los parámetros para ajustar y T L. BAliBASE, por otra parte, comprende una gran variedad de secuencias de prueba para la adaptación global múltiples. Consta de 139 series de secuencias, cada una de las cuales contiene varios bloques básicos, por lo que existe un total de varios cientos de bloques básicos que se utilizan para poner a prueba la adaptación de calidad. Es absolutamente imposible sintonizar un pequeño número de parámetros de tal forma que sólo funcionan bien en BAliBASE pero no en otros a nivel mundial relacionados con las secuencias de proteínas. Así, si un programa funciona bien la alineación de BAliBASE, se puede dar por seguro que también funciona bien con otras a nivel mundial relacionados con las secuencias de la proteína, aunque BAliBASE se ha utilizado para ajustar sus valores de los parámetros. De hecho, resultó que los parámetros que hemos sintonizado en BAliBASE trabajo no sólo para estos mundiales y los datos de los ensayos, sino también en el artificial totalmente diferentes secuencias de prueba local de IRMBASE.

El verdadero problema con BAliBASE es su fuerte sesgo hacia el mundo relacionados con la secuencia fija. Esto no se refiere sólo a la selección de las familias de proteínas que se incluyen en BAliBASE. Como se ha mencionado anteriormente, muchas secuencias de la proteína en la versión actual de BAliBASE no son del mundo real de secuencias de proteínas, pero se han truncado artificialmente por los desarrolladores de BAliBASE para que sean relacionadas con el mundo. Con estos no realistas secuencias de pruebas globales, la BAliBASE autores llevó a cabo un programa sistemático de evaluación y - no es sorprendente - descubrió que la alineación mundial de los programas en general, mejores resultados que los métodos locales [26]. El panorama podría haber sido totalmente diferente si realista de larga duración proteínas se habían utilizado en lugar de las secuencias de truncado. Para contrarrestar el sesgo hacia mundial de prueba en BAliBASE, hemos creado un nuevo conjunto de datos de referencia que consiste en simular conserva incrustado en dominios no relacionados con las secuencias aleatorias. El desempeño de los programas de adaptación en las secuencias artificiales no debe sobre-estima como el diseño de esos conjuntos de datos es necesariamente arbitraria. Sin embargo, nuestras pruebas simuladas sobre estos datos dan una impresión aproximada de la manera en que los distintos métodos de realizar la adaptación de los conjuntos de datos relacionados con el nivel local. Más estudios sistemáticos deben llevarse a cabo para evaluar el desempeño de múltiples proteínas aligners en condiciones muy variables utilizando, por ejemplo, el de larga duración BAliBASE secuencias o de nuevo desarrollo, bases de datos, como punto de referencia SABmark [27, 28], [8] Prefab o Oxbench [21].

Como conclusión de la observación, nos gustaría abordar una limitación fundamental de la mayoría de los múltiples métodos de alineación, incluyendo la que se presenta en este documento: estos métodos asumir implícitamente que homologías y conservadas motivos ocurrir en el mismo orden relativo dentro de las secuencias de entrada. Hay dos razones principales para hacer esta suposición. En primer lugar, una orden de la preservación de múltiples alineación que representa homologías brecha mediante la inserción de caracteres en la entrada de secuencias proporciona una cómoda visualización de las homologías. En segundo lugar - y que es más importante -, el auto-preservación limitación reduce considerablemente el ruido creado por azar similitudes. Un programa que devolvería todos detectables local o mundial similitudes entre las secuencias de entrada sin limitaciones de los mencionados procedimientos necesariamente regresar muchas similitudes espurios aleatorios. Para reducir este ruido, umbral arbitrario parámetros tendrían que ser aplicadas, que, a su vez, podría impedir que un programa a partir de la detección de algunas de las homologías real. Con la limitación que se ordena implícitamente impuesta por la mayoría de los programas de adaptación, la debilidad de homologías se puede detectar, a condición de que sean compatibles con el orden de otras detectado similitudes, es decir, si encajan en una sola salida de la alineación. Muchos eventos evolutivos como inserciones, supresiones y sustituciones de preservar el orden relativo homologías entre secuencias. En esta situación, respetando el orden de los métodos de alineación, en principio, son capaces de representar todos los verdaderos biológica homologías en una alineación múltiple. No obstante, alejadas de las familias de proteínas, no para la preservación de eventos como las duplicaciones o translocaciones necesidad de ser tenido en cuenta. Este tipo de acontecimientos juegan un papel importante en el análisis comparativo de las secuencias genómicas que se convirtió en una importante área de investigación en los últimos años [20]. Recientemente, algunos prometedores para múltiples algoritmos de alineamiento de las secuencias genómicas se han propuesto que sean capaces de tratar con no-para la conservación de los eventos evolutivos [22, 3]. Nuevos progresos en la alineación de múltiples proteínas se puede esperar si estas ideas se apliquen a los algoritmos de alineamiento de proteínas.

DIALIGN-T está disponible en el Servidor de Cálculo de Göttingen Bioinformática (GOB-ICS):

• Nombre del proyecto: DIALIGN-T

• Proyecto página: http://dialign-t.gobics.de

• Sistema operativo (s): UNIX y LINUX

• Lenguaje de programación: C

• Otros requisitos: ninguno

• Licencia: GNU LGPL

• Las restricciones a la utilización por los no académicos: ninguno

Un programa conjunto con funcionalidades para calcular los alineamientos de secuencias de ácidos nucleicos estará disponible muy pronto.

ARS concebido el nuevo heurística, ejecutado el programa, construido IRMBASE, hizo la mayor parte de la evaluación y la menor escribió partes del manuscrito; JWM participó en la evaluación de programas; MK proporcionado recursos; BM supervisó el trabajo, siempre y escribió la mayoría de los recursos del manuscrito.