Super paramagnética agrupación de secuencias de proteínas

Numerosos proyectos de secuenciación del genoma-han causado un rápido crecimiento de las bases de datos de proteínas. En contraste con la era pre-genómica, cuando la selección de las secuencias era muy sesgada hacia el conocido y caracterizado los genes, la exploración sistemática de los genomas permite ahora a asignar más precisos y propiedades funcionales en la mayoría de los casos. Sin embargo, la anotación manual de las secuencias es laborioso y costoso. Por lo tanto, hay un fuerte interés en el desarrollo de métodos fiables para la automática clasificación funcional de las secuencias del genoma que emplean secuencias de la evolución tal como se refleja en la utilización de homología de secuencia para predecir propiedades funcionales. La identificación de las familias de proteínas, que se define como conjunto de proteínas con un peso significativo en la codificación de similitud de secuencias de al menos relacionados con idéntica función, pero a menudo entre los miembros, es muy importante subtarea para lograr este objetivo fundamental. En efecto, el hecho de que las proteínas con alta similitud de secuencias comparten una historia evolutiva común se acepta como base para la asignación funcional [1].

Entre los distintos métodos propuestos para organizar la secuencia de las familias de proteínas en el espacio, varios enfoques basados en la similitud de secuencias utilizando la agrupación resultados fueron establecidas con éxito (véase, por ejemplo, [2 - 4]]. Sin embargo, el dominio de múltiples composición de las proteínas, así como la presencia de dominios promiscuo puede influir en la exactitud de tales métodos. Recientemente, un algoritmo eficiente para la detección a gran escala de proteínas de las familias basado en el algoritmo de cluster Markov, TRIBU-MCL, se propuso [5]. Este algoritmo simula paseos al azar dentro de un gráfico iterativo por la alternancia de dos operadores llamada "expansión" (explora dentro de la estructura de grupo) y la inflación (elimina el flujo entre los distintos grupos). En comparación con otros algoritmos de agrupación, el TRIBU-MCL produce grupos que se oponen a la contaminación por promiscua dominios que podrían proporcionar importantes problemas a otros algoritmos de agrupamiento como se discute en otra parte [6]. TRIBU-MCL fue probado utilizando grandes bases de datos de secuencias de proteínas manualmente anotado como SwissProt [7] y [8] SCOP y ya ha sido ampliamente utilizado en la bioinformática (alrededor de 50 publicaciones a que se refiere este algoritmo desde su publicación en 2002 [5], de acuerdo a [9]]. Por lo tanto, este método es una de las reconocidas herramientas bioinformáticas y sus resultados pueden ser utilizados como un estándar establecido para la comparación de los nuevos algoritmos. Por otra parte, ya hemos utilizado el algoritmo MCL TRIBU-para el análisis de la base de datos SIMAP [10].

Varios métodos de la agrupación han aparecido en los últimos años. Una de ellas, la Agrupación de Super paramagnético (CPE) ha recibido considerable atención en el análisis de microarray de datos [11, 12]. Este algoritmo proporciona agrupación de los datos de entrada [13] basada en la analogía con la física de un heterogéneo ferromagnet. El método detecta naturales (física) los grupos presentes en los datos y es capaz de difícil prueba, el grupo de manera eficiente ejemplos, como los círculos concéntricos. El algoritmo de RCP fue también utilizado con éxito en una supervisado para analizar secuencias de proteínas y de la SCOP y CATH clasificar las proteínas de acuerdo a su FSSP resultados [14]. Después de nuestra primera aplicación con éxito de la RCP a una base de datos de dominios RING-dedo de la mano [15] y nuestro enfoque de los proyectos de expresión a los datos conocidos módulos funcionales [16], el presente estudio investiga además el poder de la RCP al grupo de proteínas de las secuencias de dos grandes bases de datos , SwissProt y SCOP. Se comparan sus resultados con el algoritmo MCL-TRIBU. Desde estas dos bases de datos no contienen secuencia completa del genoma de un planteamiento imparcial necesarios para la comparación de los métodos, que, además, analizaron las secuencias de proteínas de cuatro genomas bacterianos, es decir, Bacillus subtilis, Helicobacter pylori, Listeria innocua y Listeria monocytogenes manualmente anotado en MIPS según FunCat [17 -- 19]. También introducir una extensión de este algoritmo, RCP o gSPC mundial, que realiza la agrupación por etapas en diferentes niveles de conectividad entre los puntos y ofrece un mejor rendimiento significativamente a la anotación de su conjunto en comparación con los genomas tanto el algoritmo original de RCP y TRIBU-MCL.

Pusimos a prueba la capacidad de la RCP método para determinar el número de grupos de física de los datos utilizando datos sintéticos. El problema del modelo de la figura 1 consta de n = 60 puntos en D = 2 dimensiones. Los puntos de datos se generaron utilizando tres distribuciones normales N (x _i, σ = 1,5), con centros de x ₀ (1, 2) (n = 60 muestras), x ₁ (10, 2) (n = 30) y x ₂ (14, 2) (n = 30). Los puntos de datos generados por la segunda y la tercera son la superposición de las distribuciones normales. Además tres puntos, x = (4,5 + 1,5 * j, 2), j = (0,1,2) se añadieron a simular un vínculo artificial entre los puntos de datos de la 1 ^ª y 2 ^ª distribuciones.

Figura 1 demuestra que la RCP (K = 10) fue capaz de determinar correctamente la presencia de tres grupos en los datos. Dos divisiones de las agrupaciones en la temperatura T = T = 0,054 y 0,084 se observan. La primera escisión se corresponde con una separación de los grupos formados por la 1 ^ª y otras dos distribuciones. El segundo corresponde a un split separación de las agrupaciones formadas por 2 ^ª y 3 ^ª distribuciones. Tras estas dos pausas, el grupo se derrite sobre singletons. Así, la estructura jerárquica de los datos fue descubierto física y agrupaciones presentes en la recopilación de estos datos. El ruido entre los puntos de datos de las distribuciones 1 y 2 (círculos verdes) no afectará a la agrupación de los resultados.

En contraste con RCP, el TRIBU-MCL algoritmo tiene algunas dificultades para determinar correctamente la estructura de los datos. Por ejemplo, la inflación de 2,1 parámetro, el algoritmo subclusters puntos generados por la distribución normal de 1 en 2 diferentes subclusters. Para la inflación valor de 5, se puede observar ya 5 diferentes categorías. Una de las más grandes agrupaciones contiene 21 puntos, incluidos 6 y 15 puntos generados por la distribución de 2 y 3, respectivamente. Este grupo se mantiene estable incluso en el caso de la inflación parámetro 20. Así TRIBU-MCL no puede detectar la estructura física de este conjunto de datos. Por supuesto, no se debe sacar una conclusión general sobre el rendimiento relativo de los dos algoritmos siguientes un solo ejemplo simulado.

El rendimiento de los algoritmos se investigó utilizando SwissProt [7] y SCOP [3, 8] bases de datos. La precisión de la agrupación para el SPC SwissProt base de datos se evaluó mediante el análisis de dominios InterPro [20] y suizos palabras clave de los miembros de las agrupaciones calculado. Secuencias sin ninguna anotación se utilizaron datos de la agrupación, pero no se consideraron para calcular el rendimiento de los métodos. Lo ideal sería que todos los miembros de cada grupo debería haber detectado exactamente de la misma anotación en términos de InterPro dominios y suizos palabras clave.

Análoga a la anterior, el análisis [5] sólo las agrupaciones que figuran por lo menos 4 o más se consideraron secuencias anotada. El dominio (o palabra clave) detectó combinación de ≥ 50% anotado secuencias de la agrupación fue utilizada como la anotación (consenso) de la agrupación. Desde algunas proteínas había más de un dominio (o palabra clave), que mide el rendimiento por el método de contar el número de dominios asignados correctamente y no por el número de clasificados correctamente las proteínas. Este procedimiento evita las ambigüedades en los casos en que, por ejemplo, la anotación de tres de los cinco dominios se predijo correctamente. El número de verdaderos positivos (VP) dominios y palabras clave se determinó como el conde de dominios y palabras clave que coincidió con el racimo de anotaciones. El número de falsos negativos (FN), es decir, dominios y palabras clave observado por un particular proteínas, pero ausentes en el grupo de anotación, y falsos positivos (FP), es decir, dominios y palabras clave se presentan en el grupo de anotación, pero perdió para algunos particular proteínas, se calcularon . Estos números se utilizaron para calcular la sensibilidad = TP / (TP + FN) y especificidad = TP / (TP + FP) de la agrupación de los algoritmos analizados. La sensibilidad es equivalente a la probabilidad de predecir correctamente algunos clasificador mientras que la especificidad se define como la probabilidad de que la predicción es siempre correcta [21].

No todas las proteínas inicialmente utilizados en la evaluación se tiene la oportunidad de ser anotado por la agrupación. Algunas proteínas no se agrupan en absoluto, porque no disponen de importantes éxitos a otras proteínas. Estas proteínas pueden ser tratados como falsos negativos (de hecho, sus categorías no prevista) o simplemente excluidos de los análisis (ya que no se pueden agrupar en cluster y el algoritmo expresamente "negado" a los comentarios). La sensibilidad que se calcula teniendo en cluster proteínas parece ser más pertinente. En efecto, si una proteína se agrupaba, la sensibilidad determinada, en nuestro estudio, se indicará el número de las categorías existentes de la proteína analizada se espera que se predijo correctamente. Esta definición se refiere a la sensibilidad a posteriori, es decir, que sólo debe utilizarse después de la agrupación de familias de proteínas. La sensibilidad determinada por considerar todos los no agrupados proteínas como falso positivo, corresponde a la sensibilidad a priori. De hecho, este número indica el número de categorías de la proteína dada se predijo correctamente cuando no hay conocimiento si una proteína se agruparán o no. Desde cada una de estas dos definiciones de la sensibilidad tiene su propia ventaja (por ejemplo, el posterior permite una más fácil comparación de los métodos), se calcularon los dos. Notificación, que esta definición de la especificidad no incluye FN y, por tanto, no es afectado por la definición que se utiliza.

AP secuencias de la base de datos [22] (Levantamiento del 01/07/2003) se agruparon después de la eliminación de las entradas redundantes. Estas secuencias fueron anotados utilizando la base de datos SCOP v. 1,63 [3, 8]. La TRIBU-MCL resultados se calcularon usando el valor de la inflación de 5 [5]. El número total de las proteínas se utilizan para el análisis 15605 y 12961 de las secuencias había asignado SCOP dominios. El número total de dominios se manualmente comisariada 13070 dominios. Ambos anotada y no anotada proteínas se utilizaron para la agrupación. Es evidente que el método de ejecución se calculó sólo en los casos anotados.

El SPC cubiertos menos el 6% para las secuencias de K = 20, aunque ha dado lugar a posteriori mayor especificidad y sensibilidad (Tabla 1]. TRIBU-El MCL, sin embargo, produjo una mayor sensibilidad a priori. Para este valor de K, tanto el CPE y TRIBU-MCL datos agrupados en aproximadamente el mismo número de racimos. Más grandes valores del parámetro K aumentado aún más el número de cubiertos secuencias, pero disminuyó el rendimiento de RCP. Por ejemplo, un aumento de K de 20 a la utilización de todas las conexiones ( "todos los NN") que abarca 330 secuencias adicionales. El número de verdaderos positivos predicciones aumentó en 183. Sin embargo, este aumento fue acompañado por un adicional de 173 falsos negativos y 147 positivos predicciones falsas, con lo que disminuye el rendimiento general. No todas las secuencias son idénticas para ambos casos. El "20" de las agrupaciones que figuran 300 secuencias que estuvieron ausentes en "todos los NN" agrupaciones. De la misma manera, existen 630 secuencias que se presente en "todas las NN", pero los grupos estuvieron ausentes en el "20" de las agrupaciones. El desempeño del algoritmo para estas 630 nuevas secuencias de verdadera era de 569 positivos, 63 falsos negativos y 61 positivos falsos. Esto corresponde a 90% de sensibilidad y especificidad.

Así, la actuación de la agrupación método utilizando todas las conexiones no disminuyen drásticamente debido a la adición de las nuevas secuencias, sino más bien por su peor pronóstico de algunas secuencias que ya estaban en cluster utilizando K = 20. Por lo tanto, uniéndose a los resultados calculados usando la variable K valores y la preservación de los resultados calculados para las secuencias que se agruparon en cada paso anterior, se puede esperar tanto para aumentar la sensibilidad y especificidad del método. De hecho, el uso de la gSPC método previsto un aumento considerable en el rendimiento de la agrupación. El número de falsos positivos y falsos negativos de la "NN todos los" grupos fue inferior a la calculada utilizando números fijos valor de K = 20, pero tantos como 610 nuevas secuencias fueron cubiertos. El método gSPC superaron a los TRIBU-MCL y SPC en términos de a priori y a posteriori sensibilidades. Así, el rendimiento de la gSPC era considerablemente mejor que los otros métodos, tanto en términos de cubiertas y de la calidad de las secuencias de anotación. Esta mejora es de gran importancia para una anotación automática de secuencias de proteínas.

El InterPro dominios (v. 6.1) abarca 112935 (89%) secuencias de la base de datos SwissProt Release 41,9 (126798 secuencias). El número total de 235672 dominios se calculó para este conjunto. El MCL TRIBU-97792 secuencias agrupadas en racimos 6200 que figura anotado al menos 4 proteínas (Cuadro 2]. El consenso siempre anotación 93,8% de especificidad para estos datos. La misma especificidad de la CPE, el 94,1%, se ha calculado para K = 20 vecinos más cercanos. El número de secuencias cubiertos por el algoritmo de RCP fue 96716. El uso de la gSPC hecho posible que atender alrededor de 7000 nuevas secuencias con especificidad y "a posteriori" a posteriori "la sensibilidad de 95,2% y 94%, respectivamente.

SwissProt La base de datos proporciona un vocabulario controlado de 878 palabras clave que ha sido utilizado por muchos investigadores para probar diferentes algoritmos de clasificación. El número total de 490065 casos, la palabra clave fue asignado a 125248 proteínas. En cuanto al análisis de la InterPro ámbitos, el análisis que se gSPC mayor rendimiento y abarca un mayor número de secuencias de proteínas en comparación con el uso de un solo valor o K-TRIBU-MCL algoritmo (Tabla 3].

Para este análisis de las secuencias de proteínas 11502 de cuatro genomas secuenciados completamente, Bacillus subtilis, Helicobacter pylori, Listeria innocua y Listeria monocytogenes, se utilizaron. La anotación de los genomas se hizo en MIPS usando FunCat 1,3 [17]. El FunCat es una anotación para el régimen de la descripción funcional de las proteínas de procariotas, eucariotas unicelulares, plantas y animales [17, 18]. Teniendo en cuenta el amplio espectro y muy diversas funciones de la proteína conocida, FunCat consta de 28 principales categorías funcionales (o ramas), que en general abarcan campos como el transporte celular, el metabolismo y la transducción de señales. Las principales ramas exhiben una jerárquica, árbol como la estructura con un máximo de seis niveles de creciente especificidad. En total, el 1,3 incluido FunCat categorías funcionales, y en 1445 un total de 403 categorías distintas y estaban disponibles para analizar los genomas bacterianos. El manual de clasificaciones funcionales fueron presentadas durante 6354 proteínas.

Una estimación del rendimiento de las proteínas que tienen similar, pero no exacto anotación representan un reto. Veamos un ejemplo de un grupo que contiene tres proteínas. La primera proteína que tiene anotación

01.01.01.01.02, la biosíntesis de glutamato grupo

01.05.01, C-compuestos y la utilización de carbohidratos

40,03, citoplasma

La segunda proteína ha anotación

01.01.01.01.02.01, biosíntesis de la prolina

40,03, citoplasma

Y la tercera es la proteína anotado con una categoría única:

01.01.01.01.02, la biosíntesis de glutamato grupo

La anotación de las tres proteínas es similar, pero la anotación de la segunda proteína es más detallado para el metabolismo de la categoría (01) mientras que la primera contiene proteínas categoría adicional 01.05.01. La tercera proteína no tiene una anotación en la categoría 40, localización subcelular.

Se midió el rendimiento de anotación contando el número de todos los que no sean redundantes subcategorías, es decir, 01, 01,01, 01.01.01, etc En el ejemplo anterior el consenso anotación de este grupo es 01.01.01.01.02 y 40,03 categorías (incluidas todas las Sus sub-categorías). El número de anotaciones es TP 19 = 7 + 7 + 5. El número de FN es de 3. Estos son sub-categorías 01,05, 01.05.01, y 01.01.01.01.02.01, para la primera y segunda proteínas, respectivamente. También hay dos anotaciones FP, 40 y 40,03 para la tercera observó proteína.

El desempeño de los tres algoritmos se muestra en la Tabla 4. El número total de la no redundante subcategorías para este análisis fue 44531. Los métodos calculado un rendimiento similar, pero el algoritmo gSPC abarca un mayor número de secuencias. Por lo tanto, el rendimiento de gSPC fue notablemente superior en términos de la sensibilidad a priori.

El cuadro 5 se resume la comparación de los tres métodos, en términos de cubiertas y el total de secuencias de errores. En general, el uso del algoritmo de gSPC traducido en un mayor rendimiento de todos los ejemplos y abarca un mayor número de secuencias.

Hemos descrito y demostrado el uso y el rendimiento de la RCP y de su extensión, gSPC, de la agrupación de secuencias de proteínas utilizando secuencia única similitud. Por primera vez, el RCP algoritmos para agrupar secuencias de proteínas ha sido utilizada en un estudio a gran escala. Nuestros resultados confirman que este método es una valiosa y fiable herramienta automática para la clasificación funcional de las secuencias de proteínas.

El uso de la agrupación por etapas, gSPC, la mejora de la sensibilidad y especificidad del método original y nos permitió obtener una mayor precisión en comparación con el TRIBU-MCL y original SPC algoritmos utilizando conjuntos de datos de AP y de las bases de datos SwissProt. El desempeño de la gSPC para anotación de Suiza Palabras clave se compara favorablemente con los enfoques de la supervisión. Por ejemplo, el porcentaje de secuencias cubiertos por gSPC para el 93,7% (K = 6) y 93% (K = 20), la especificidad fueron de 62% y 79%, respectivamente. El primer número es similar a la calculada por el método de clasificación supervisada utilizando el algoritmo C4.5, donde el 58% de las secuencias fueron cubiertos con un 94% de especificidad [23]. Así, el algoritmo de clasificación SPC rendimiento es comparable a la situación actual de arte bajo la supervisión de aprendizaje automático de clasificación utilizado por [23]. Aviso, que este último método utilizado diferentes atributos de la secuencia, tales como PFAM dominio y PROSITE composición, y, por tanto, tuvo en cuenta explícitamente la organización multi-dominio de las proteínas. El algoritmo de RCP, en contra de lo que, la secuencia utilizada sólo similitud. Este resultado indica alta capacidad de predicción de la anotación utilizando gSPC agrupación.

La especificidad de la gSPC algoritmo usando todas las conexiones ( "todos-NN"), el 92,8%, es también ligeramente superior a los resultados de otro enfoque de la supervisión, el algoritmo de adaptación automática de anotación [24] calculó que un 90,4%. Estos resultados, sin embargo, son sólo indicativos ya que nuestros planteamientos anteriores y son diferentes con respecto a sus tipos (es decir, bajo supervisión y sin supervisión). Además similares, pero no idénticos conjuntos de datos se utilizaron. Por ejemplo, el rendimiento del algoritmo adaptativo [24] fue probado usando secuencias de la sonda 500, seleccionados en forma aleatoria, de SwissProt mientras que el rendimiento del algoritmo C4.5 fue probado utilizando 10 veces la validación cruzada.

Una ventaja importante de la agrupación sin supervisión de enfoques sobre la supervisado unos es la capacidad de la ex métodos para detectar todavía incumplido las relaciones entre las proteínas. Tales resultados podrían utilizarse para encontrar nuevas familias de proteínas que en la actualidad no tienen o han funcional anotaciones incompletas o incoherentes. Los métodos sin supervisión tampoco están sujetos al riesgo de problemas de overfitting. Overfitting menoscaba el poder predictivo de los criterios para la supervisión de muestras que no estuvieron representados en el conjunto de formación [25 - 27].

El gSPC provocado el incremento de la sensibilidad y especificidad de todos los conjuntos de datos analizados. El uso de la sensibilidad a priori hizo posible comparar los resultados de todos los métodos a través de una serie de muestras y de hecho la comparación más sencilla. Sin embargo, desde un punto de vista práctico, en particular para la aplicación de las líneas de tubería de anotación de genomas completos de la especificidad y la sensibilidad a posteriori y no a priori, la sensibilidad son los factores más importantes de la anotación automática. De hecho, es preferible anotar un menor número de secuencias en el modo automático con una precisión superior a la que registran un mayor número de ellos con menor precisión. Las secuencias no automáticamente anotado por el algoritmo puede ser anotado posteriormente por métodos complementarios o por cuidado de dominio manual de análisis de la estructura de las secuencias. Cualquier intento de aumentar la sensibilidad a priori y, por tanto, abarcar un mayor número de secuencias por la reducción de la especificidad puede dar lugar a un desempeño inaceptable para la anotación.

El SPC algoritmo calcula árbol jerárquico de las estructuras de las agrupaciones K para cada valor. En nuestro análisis hemos identificado y considerado sólo la hoja de grupos. La parte superior del árbol se pasó por alto. Este análisis fue posible, ya que los datos analizados en este estudio con el mayor número de secuencias de proteínas se agruparon en hojas y sólo algunas secuencias pueden ser agrupadas aún teniendo en cuenta el conjunto de estructura de árbol. Por ejemplo, con K = 6 (Cuadro 1 y 2, SPC resultados) sólo 56 y 627 secuencias adicionales podrían agruparse para la AP y SwissProt conjuntos de datos, respectivamente. Estas cifras corresponden a alrededor de un 1% en cada base de datos de secuencias y sólo marginalmente influido en el método de ejecución. El gSPC algoritmo, como se ha mencionado en la sección Método, agrupadas en esas secuencias de mayor K valores. Esta mejora de la predicción de su desempeño en comparación con el original método de RCP.

El desempeño de cualquier algoritmo de análisis de secuencia de las relaciones depende de la selección de los conjuntos de datos de referencia. La composición de los conjuntos de datos, tales referencias podrían sesgar los resultados, ya que en realidad la selección de las secuencias de genomas conocidos o bases de datos no es una muestra aleatoria representativa de la secuencia espacial. Por ejemplo, la SCOP SwissProt y las bases de datos son muy a menudo utilizados como "estándar de oro" para la anotación y métodos de clasificación. Sin embargo, estas bases de datos representan un sesgo de selección y no abarcan todo el genoma. Por lo tanto, el análisis del desempeño de los métodos de la agrupación está sesgado por la composición de los conjuntos de datos de referencia. Por ejemplo, el gSPC disminuido missassignments por 2-5% para estos dos conjuntos. Dado que la tasa de error de las secuencias de estos agrupan conjuntos de datos fue de aproximadamente 10-15% (Tabla 5], la relativa ganancia en el rendimiento fue 10-40%. En otras palabras, la anotación automática de secuencias agrupadas con gSPC hará que hasta un 40% menos errónea anotaciones (falsos positivos o falsos negativos anotaciones), en comparación con otros métodos. Por otra parte, los tres métodos devuelto resultados similares para los genomas bacterianos. Para este conjunto gSPC abarca alrededor del 12% de las secuencias adicionales que es muy importante para la anotación del genoma.

GSPC El método desarrollado es rápido. Un análisis completo de la AP y SwissProt de datos utilizando todos los niveles de toma de K moderados ordenador PC (AMD 1,3 GHz) con menos de 14 y 120 minutos, respectivamente. La velocidad del algoritmo original SPC escalas aproximadamente lineal con el número de conexiones. Este número aumenta aproximadamente como N ² con el número de muestras. Sin embargo, desde gSPC usos etapas agrupación, el número real de las muestras restantes de la agrupación K utilización de grandes valores es pequeño. Por lo tanto, la velocidad gSPC está determinado principalmente por el uso de agrupaciones pequeñas, K = 2-6, y los valores en la práctica es aproximadamente lineal con el número de muestras. De hecho, el método será lo suficientemente rápido de manera eficiente a la categoría de datos con millones de secuencias; agrupación computacional requisitos, por lo tanto, es pequeño en comparación con el cálculo de las puntuaciones de similitud de secuencias. La eficiencia computacional es claramente una ventaja gSPC método de la comparación con el TRIBU-MCL. La complejidad de las escalas más tarde como O (N ²⁾ N es el número de elementos no-cero en la matriz. Por lo tanto, este método funciona más lento, si un creciente volumen de información genómica tiene que ser procesado.

El gSPC calculada con mayor precisión o cubierto un mayor número de secuencias que el TRIBU-MCL algoritmo para el conjuntos de datos analizados. La exactitud de la anotación de gSPC para la base de datos SwissProt es comparable a la de los métodos supervisados. Por lo tanto, es un enfoque útil para la detección automática de las familias de proteínas y anotación de genomas completos.

SPC realiza una estrategia de agrupación jerárquica [13]. Los datos de entrada para el SPC se representa como una matriz de la distancia d _ij (especificado por el usuario) entre los puntos de datos i = 1 ,..., N. Esta matriz se utiliza para crear un gráfico, cuyos vértices son los puntos de datos y los bordes correspondientes a los puntos de conexión entre vecinos. Cada dos puntos se consideran los vecinos (y, por tanto, tienen una ventaja), si están dentro de K vecinos más cercanos unos de otros (K-mutuo-vecino criterio). Ferromagnéticos en el modelo de cada uno de los puntos se considera que tiene una tirada Potts, equivalente a un número entero de valores de q, s = 1,2, ... q. Pares de puntos vecinos i y j que tienen el mismo spin s _i s = _j interactúan con fuerza J _ij, que es una función de una primera matriz de la distancia d _ij [13].

Una simulación de Monte Carlo utilizando el método de Swendsen-Wang (SW) [28] se utiliza para determinar los grupos de puntos. La simulación comienza con la asignación de un spin Potts aleatoria a cada punto de datos en el conjunto de datos. Los vecinos con puntos idénticos gira interactuar unos con otros. La probabilidad de que estos puntos pertenecen al mismo grupo de SW (es decir, instantánea grupo resultante de una iteración) se calcula como P _ij = (1 - exp (- J _ij / T)), donde T es la temperatura algunos fijo. Los puntos de la misma agrupación SW recibir idéntico spin (seleccionados por el azar) para la próxima iteración. Las repeticiones se realizan hasta que la convergencia observada utilizando, por ejemplo, autocorrelación tiempo [29].

Para la agrupación, los puntos fuertes de los bordes de la red se calcula con la spin-spin función de correlación G _ij. Esta función se calcula como el cociente de iteraciones cuando los puntos i, j pertenecen al mismo grupo de SW versus el número total de iteraciones durante la simulación. Aviso, que si los valores de P _ij determinar un instante la probabilidad de que dos puntos con el mismo spin que pertenecen al mismo grupo instantánea (es decir, locales de la conectividad), el spin-spin correlación función tiene en cuenta las múltiples interacciones en medio de los puntos, es decir, la conectividad global De la red. En realidad la conectividad global determina la probabilidad de dos puntos tendrán el mismo giro. A temperaturas muy bajas, incluso las pequeñas J _ij causa vecinas a los puntos tienen la misma tirada, G _ij ≅ 1, es decir, el sistema está en el estado ferromagnético. Si la temperatura es muy alta, entonces todos los J _ij <<T, y la probabilidad de encontrar cada par de puntos vecinos en el mismo estado que disminuye el valor esperado por azar G _ij ≅ 1 / q. Así, el sistema está desordenada, es decir, en el estado paramagnético. Si los valores son iguales acoplamiento J _ij = J, sólo dos estos estados son estables. El sistema tiene una fuerte transición de la ferromagnético a la paramagnética estado a cierta temperatura.

En caso de un sistema heterogéneo, algunos magnetica "granos" se puede observar. Esos grupos tienen fuertes puntos de conexión entre los miembros y sólo la debilidad de las conexiones a todos los puntos fuera de la agrupación. Cada grano tiene su propia temperatura de transición de la ferromagnético al estado paramagnético. En algún rango de temperatura, el llamado estado superparamagnético, el sistema puede contener algunos puntos en un nivel local y estatal ordenó ferromagnéticos, así como otros en un local desordenada paramagnética estado. Al final de la simulación, todos los puntos que había spin-spin correlación _G ij> 0,5 formar un grupo. Los puntos que habían G _ij <0,5 puede ser conectado a sus vecinos con la máxima G _ij. Los resultados del análisis a diferentes temperaturas, se combinan y proporcionan una agrupación jerárquica de los datos. Una descripción más detallada de la CPE puede encontrarse en otro lugar [13].

Libre parámetros de la Ficha Técnica algoritmo de incluir el número de vueltas q en el modelo de Potts, el número de vecinos más cercanos K para el K-mutuo-vecino criterio, y el número de iteraciones que para el algoritmo de SW. Un aumento de q requiere un mayor número de iteraciones para la convergencia, pero de otro modo no afectó el rendimiento del algoritmo [30]. Para q = 20 la convergencia de SW algoritmo se observan generalmente usando I = 1000 iteraciones para la gran mayoría de los casos investigados. Los mismos valores también dio lugar a la convergencia de los algoritmos de las bases de datos utilizadas en nuestro estudio.

Como se ha descrito anteriormente, SW simulaciones de comenzar con la configuración de spin azar. Tras posteriores iteraciones, el algoritmo converge en un estado estable, que no depende de la configuración inicial. Habida cuenta de la convergencia a una cierta temperatura, se puede esperar que la configuración debe ser similar a los convergentes de estado de el siguiente paso en lo que respecta al aumento de la temperatura. Así, si SW simulaciones se comenzó desde un estado convergieron calculado para una temperatura similar, la convergencia para el nuevo Estado debe ser más rápido. Sin pérdida de la precisión, hemos utilizado este hecho para acelerar simulaciones SW. La configuración tras la finalización de cada ciclo de simulación se salvó y lo usó como el inicial para el próximo temperatura. Es posible disminuir el número de iteraciones de 1000 a I = I = 200, sin afectar la calidad de los resultados.

El K-mutuo-vecino criterio de los controles de la resolución de la agrupación. Un bajo valor K toma en consideración sólo el más cercano pares de puntos conectados entre sí (es decir, conexiones de corto "). Como sus valores aumenta, las conexiones de largo alcance también se tomen en consideración y que participen en el proceso de agrupación. En estudios previos se ha seleccionado este parámetro en el rango de 5-20 [13, 30]. En un estudio reciente [31] un algoritmo para determinar los valores óptimos K Se propuso también. El valor óptimo de K corresponde a la máxima estable particiones caracteriza por anchuras máximas de la superparamagnético dominios. La optimización de K es crítica en la falta de información fiable de clasificación para permitir el aprendizaje supervisado. En este estudio, fiable familia de proteínas cesión de los ensayos y la formación se dispone de datos. Así, es posible analizar directamente el rendimiento de la RCP algoritmo como una función del parámetro K.

El uso de un valor constante para K es razonable si el conjunto de datos es bastante homogénea. En este caso, los datos que tienen los mismos puntos de conexión en promedio. En realidad, el problema de la secuencia de asignación basado en la familia es complejo. Algunas familias de proteínas aparentemente la base de las limitaciones relativas a la variación de su secuencia y contienen un gran número de secuencias muy similares, mientras que otros contienen sólo algunas familias de los miembros que muestra similitud de secuencia baja. Utilizando los valores óptimos de K conservadas familias pueden sesgar el proceso de agrupamiento y la reducción de la sensibilidad para descubrir las más divergentes. Por lo tanto, no es conveniente utilizar un solo valor-K para la agrupación de todos los datos.

En este artículo presentamos un análisis por etapas utilizando diferentes K-valores. Los datos se agrupan en consecuencia, utilizando K = 2, 6, 20, 64 y K = "todas" las conexiones. Esta elección de K corresponde aproximadamente a un 10 veces mayor en la conectividad de datos que es proporcional al K ^2. Para cada K, que varía desde un mínimo de temperatura, T = 10 ^-4, a un máximo, T = 2, los valores. En el valor máximo de la categoría T no se observó. Tan pronto como un subconjunto de las secuencias se agrupan a través de algunos K, que fueron retirados de un análisis ulterior, salvo un representante secuencia. El representante secuencia fue la que tuvo la mínima suma de las distancias a las otras secuencias en la agrupación. Estas secuencias de representante, así como todas las otras restantes no agrupados secuencias se utilizaron para la siguiente ronda, es decir, mayor K, de análisis. Esa agrupación de abajo a arriba nos permitió cubrir los diferentes tipos de agrupaciones que abarcan una amplia gama de homogeneidad y de mejorar el funcionamiento del método, como se muestra en la sección de Resultados. Con el fin de distinguir el algoritmo inicial de la RCP por etapas enfoque propuesto en este estudio, nos referiremos a este último mundial como la RCP (gSPC).

El algoritmo de RCP proporcionó una agrupación jerárquica de los datos relativos a cada uno de los pasos de la gSPC análisis. Veamos el procedimiento de las agrupaciones de aumentar la temperatura. T = 0 para todas las secuencias de formar un grupo que empieza a derretirse y romperse en subclusters a medida que la temperatura aumenta. Las agrupaciones de diferentes tamaños pueden aparecer y luego se derrite a altas temperaturas. Algunos grupos pueden contener únicamente las secuencias de 2-3 mientras que otros grupos constan de más de mil secuencias. Un número de grupos perderá uno o varios miembros de algún particular, la temperatura, mientras que otros se dividirá en dos o más subgrupos. En caso de que el conjunto de datos contiene sólo pocos grupos, se puede inspeccionar el tamaño de grupo o de susceptibilidad, que es la variación de la magnetización del sistema en función de la temperatura [13, 30]. Si es diferente estable sub-fases están determinadas, por ejemplo, por cambios en los tamaños de grupo, es posible seleccionar una temperatura de cada región de interés para el análisis. Este método, sin embargo, es inviable a los efectos de nuestro estudio, cuando tantos como miles las agrupaciones de empresas pueden ser simultáneamente observado para cada temperatura. Así, la composición de cada grupo de temperatura medida debería ser considerada para el análisis y algunos enfoque automatizado para el análisis de estos resultados se debe realizar. En los párrafos siguientes se describe un método que realiza este tipo de análisis en una forma completamente automática.

Vamos a limitar el tamaño de un mínimo de cualquier grupo a algún parámetro C. Todos los puntos en los grupos que tienen el tamaño de menos de los miembros de C se consideraron como puntos o unclustered singletons. Los singletons no formaban grupos separados pero pertenecen a la agrupación de la que fueron generados. En algún particular, la temperatura puede romper un clúster (derretir) en un número de subclusters y singletons. Sin embargo, si y sólo si estos subclusters que figuran al menos dos subclusters cada uno con al menos secuencias C, el grupo de padres se consideró que se subdividiría en subclusters. De otro modo, el grupo se considera sin cambios. Una hoja grupo fue un grupo que no forma subclusters (o sea, que irrumpieron en singletons). El simple se agruparon de nuevo por el mismo procedimiento para mayor K.

En otras palabras, el resultado de la RCP utilizando una única agrupación K es un árbol jerárquico de las agrupaciones (o varios desgajaron árboles) generados por el análisis de los puntos de datos sobre toda la gama de temperaturas (de mínima a la máxima temperatura). El árbol fue procesada para detectar la hoja de agrupaciones, que se identificaron a diferentes temperaturas. Figura 2 ilustra un ejemplo de la detección de grupos de hoja de un solo K, y la figura 3 muestra el procesamiento de los datos para diferentes K.

El flujo de datos del algoritmo (ver figura 4] se resume como sigue: En un principio la secuencia similitudes se descargan de la base de datos como FASTA SIMAP resultados. Entonces, el algoritmo usando secuencias de las agrupaciones K = 2. Durante el análisis de la temperatura es escaneada de un mínimo de 10 ^-4 T = (cuando la práctica totalidad de puntos forman un gran grupo) a un máximo valor T = 2 (cuando casi todos los puntos son singletons). La hoja de las agrupaciones son detectados y utilizados para calcular el rendimiento de este algoritmo para la K (véanse los cuadros 1, 2, 3, 4]. Las secuencias de la hoja de las agrupaciones son eliminados entonces de un mayor análisis, salvo el representante más (véase más arriba). Posteriormente, aumentamos K y llevar a cabo la próxima ronda de análisis. El análisis está terminado cuando el valor máximo especificado K se alcanza. El representante secuencias pueden ser destinados a algunos grupos con diferentes K más tarde en rondas de iteración. La anotación de estas secuencias en el grupo más pequeño con K se utilizó para contar con el método de ejecución. El gSPC procedimiento, ya que fue detectado correctamente por el revisor anónimo, también depende de la temperatura de paso utilizada en el análisis de cada uno de los grupos de K. Por ejemplo, la utilización de grandes medidas, Δ T = 0,3, se podría detectar diferentes grupos de hojas en la Figura 2. Como se desprende de la misma cifra, la sensibilidad a este parámetro no es una característica particular de gSPC pero de la original SPC método que se utiliza para determinar la hoja de grupos. Así, la identificación de grupos de la hoja puede ser ambigua en algunos casos. En nuestro artículo hemos utilizado Δ T = 0,01 y no se observan cambios significativos en el desempeño del algoritmo para los valores más pequeños de este parámetro.

TRIBU-El MCL fue descargado de algoritmo [32]. Los valores de la inflación parámetro utilizado para el análisis de los datos fueron seleccionados como se indica en el estudio original [5].

Un archivo que contiene secuencias de FASTA que se utilizaron para la agrupación se comparó a sí mismo utilizando BLAST [33] de la base de datos SwissProt aplicado en PEDANT [34]. A los genomas de bacterias de la FASTA en pareja fueron las puntuaciones para el SIMAP recuperados de la base de datos [10].

La todos-contra-todos similitudes secuencia generada se analiza y se utiliza como entrada para ambos algoritmos. Los datos de entrada para TRIBU-MCL han estado representados de _log-10 (E-valor). La entrada de los valores de las RCP se distancia de los valores calculados como -1./log ₁₀ (E-valor). Pares puntuaciones con E-valor> 0,1 fueron excluidos del análisis.

PEDANT - Extracción de Proteínas, Descripción y ANalysis Tool

FunCat - MIPS funcional catálogo

TRIBU-MCL - Markov algoritmo de cluster

SPC - Super paramagnética agrupación

GSPC - RCP mundial

SIMAP - Similitud Matriz de Proteínas

IVT programado el algoritmo y se lleva a cabo el análisis de datos. AF desarrollados interfaz gráfica del algoritmo. AR anotada y proporcionó los datos de los genomas de bacterias y participó en su análisis. HWM concibió y supervisó el proyecto. Todos los autores leído y aprobado el manuscrito final.