PLoS Computational Biology, 2005; 1(1): (más artículos en esta revista)

Combinatoria Plan Discovery Enfoque para el Folding Trayectoria Análisis de una β-Horquilla

Biblioteca Pública de la Ciencia
Laxmi Parida [1], Ruhong Zhou [1]
[1] Centro de Biología Computacional, IBM Thomas J. Watson Research Center, Yorktown Heights, Nueva York, Estados Unidos de América
[2] Departamento de Química, Universidad de Columbia, Nueva York, Nueva York, Estados Unidos de América
Resumen

El estudio de los mecanismos de plegamiento de proteínas sigue siendo uno de los problemas más agudos en biología computacional. Actualmente, el mecanismo de plegado de proteínas es a menudo caracterizado por el cálculo de la energía libre paisaje de reacción frente a diversas coordenadas, como la fracción de contactos nativo, el radio de gyration, RMSD a partir de la estructura, y así sucesivamente. En este trabajo, se presenta un patrón de descubrimiento combinatoria enfoque global a la comprensión de los cambios de estado durante el proceso de doblado. Este es un primer paso hacia un sin supervisión (y quizás automatizado) enfoque hacia la identificación de los estados a nivel mundial. El enfoque se basa en la computación biclusters (el modelo o grupos) de cada grupo es una combinación de varios reacción coordenadas, y de la firma del patrón facilita el cálculo de la puntuación Z para el grupo. Para este proceso, se presenta un algoritmo de tiempo complejidad c ∈ RO RO ((N + nm) log n), donde N es el tamaño de los patrones de producción y (n × m) es el tamaño de la entrada de datos en tiempo n M marcos y coordenadas de reacción. Hasta la fecha, este es el mejor momento para la complejidad de este problema. Seguidamente, se aplican a un β-horquilla plegable trayectoria y demostrar que este enfoque de los extractos de información fundamental acerca de plegado de proteínas y mecanismo de los estados intermedios. Estamos hacer tres observaciones sobre el enfoque: (1) El método recupera los estados anteriormente obtenida por el análisis visual de las superficies de energía libre. (2) También tiene éxito significativo en la extracción de los patrones y estructuras que se habían pasado por alto en trabajos anteriores, que proporciona una mejor comprensión del mecanismo de plegado de la β-horquilla. Estos nuevos modelos también interconectar diversos estados existentes en las superficies de energía libre de reacción frente a diferentes coordenadas. (3) El método no requiere el cálculo de los valores de energía libre, sin embargo, ofrece un análisis comparable a, y, a veces, mejor que los métodos que utilizan energía libre paisajes, dando validez a la elección de las coordenadas de reacción. (Un resumen versión de este trabajo fue presentado en el 2005 en Asia y el Pacífico Bioinformática Conferencia [1].]

Introducción

Entendimiento plegamiento de proteínas es uno de los más difíciles problemas de la biología molecular [2 - 7]. El interés no es sólo en la obtención de la doble final (que generalmente se denomina estructura de predicción) [8 - 10], sino también en la comprensión del mecanismo de plegado y doblado cinética que participan en el actual proceso de doblado. Muchas veces en las proteínas globulares únicas estructuras en una escala de tiempo muy corto. El llamado carpetas rápido puede retirarse en la estructura funcional de azar bobina en milisegundos a microsegundos. Los recientes avances en técnicas experimentales que la sonda de proteínas en diferentes etapas durante el proceso de doblado han arrojado luz sobre la naturaleza de la termodinámica y la cinética de plegamiento [11 - 17]. Sin embargo, debido a limitaciones experimentales, el plegado de proteínas detallada vías siguen siendo desconocidos. Simulaciones por ordenador realizadas en los distintos niveles de complejidad, que van desde la simple celosía modelos para todos los modelos de átomo con solvente explícito, se puede utilizar para completar la prueba y llenar algunas de las lagunas en nuestro conocimiento sobre los mecanismos de plegamiento.

Simulaciones a gran escala acerca de plegado de proteínas realista con todos los modelos de átomo sigue siendo un gran reto [3 - 5, 7]. Enorme esfuerzo que se necesita para este gran problema, un ejemplo de ello es el reciente proyecto de IBM Blue Gene, que está destinada a la construcción de una supercomputadora con cientos de teraflop petaflop a la potencia de las computadoras para hacer frente al problema de plegado de proteínas. Mientras tanto, los análisis eficaz de los datos de la trayectoria de plegado de proteínas simulaciones, ya sea por la dinámica molecular o Monte Carlo, sigue siendo un desafío debido a la gran cantidad de grados de libertad y la enorme cantidad de datos trayectoria. [18, 19] Actualmente, el mecanismo de plegado de proteínas es a menudo caracterizado por el cálculo de la energía libre del paisaje frente a la así llamada reacción en las coordenadas [3, 20, 21]. Nosotros y otros han utilizado diversas coordenadas de reacción [3, 20, 21], como la fracción de contactos nativo, el radio de gyration de toda la proteína, la raíz cuadrada media desviación (RMSD) de la estructura nativa, el número de β - Filamento de hidrógeno bonos, la cantidad de α-hélice gira, el núcleo hidrofóbico de gyration Radio, y los componentes principales (PC) de un análisis de componentes principales [20, 22]. La búsqueda de una mejor reacción de las coordenadas es todavía de gran interés en el mecanismo de plegado de proteínas estudios. Estos análisis han proporcionado importante información para una mejor comprensión de plegado de proteínas. Sin embargo, se requiere a menudo, a priori, los conocimientos sobre el sistema en estudio, y los mapas de curvas de energía libre suele resultar en la reducción de demasiada información debido a su límite en la dimensionalidad, que es a menudo tan bajos como dos o tres. Así, mejor o complementarios de los instrumentos de análisis son de gran demanda.

También se sabe que el proceso de plegamiento de las proteínas tiene muchos aminoácidos que la bobina a través de diferentes estados intermedios antes de estabilizarse en el último estado doblado. Por lo tanto, un primer paso para entender el proceso de doblado es identificar a esos estados. En el presente trabajo, se propone el uso de un patrón de descubrimiento combinatoria técnica para analizar proteínas plegables trayectoria datos de los experimentos de simulación. Un aspecto novedoso de la actual algoritmo es que se incorpora arbitraria y posiblemente diferentes funciones de distribución de los datos en cada dimensión y garantías completa y precisa solución al problema de la agrupación. El procedimiento implica cálculos de las agrupaciones de los datos: cada grupo tiene un patrón de la firma que describe todos los elementos de la agrupación. La sencillez de la pauta conduce a la fácil interpretación y, por tanto, de una mejor comprensión de los procesos subyacentes y facilita el cálculo de un puntaje Z para el grupo. Redundancia de las oportunas comprobaciones, el número de grupos se hace manageably pequeños. Los resultados de este método son tres. En primer lugar, el método se validó mediante la comparación de sus resultados con los resultados publicados anteriormente con una energía libre paisaje análisis. En segundo lugar, el método tiene éxito significativo en la extracción de los nuevos patrones y estructuras que se habían pasado por alto antes. Estas nuevas estructuras de proporcionar una mejor comprensión del mecanismo de plegado de un β-horquilla, que se utiliza como un caso de estudio en este trabajo. Estos nuevos modelos también interconectar diversos estados existentes en mapas de curvas de energía libre de reacción frente a diferentes coordenadas. Este éxito nos anima a postular que el descubrimiento automático llevará a una mayor comprensión del proceso de doblado. En tercer lugar, el método valida la elección de las coordenadas de reacción desde el patrón de descubrimiento basado en el análisis de estas coordenadas reacción comparación con los anteriores planteamientos basados en la energía libre.

Resultados y Discusión
Descripción de los modelos

Bien conocidas existen métodos de simulación para llevar a cabo el plegamiento de una proteína. Sin embargo, con frecuencia no es suficiente para obtener una comprensión de sucinta el proceso de doblado. La tarea aquí es comprender el mecanismo de plegado al reconocer patrones estructurales o intermedio se establece que el proceso de doblado atraviesa. Por ejemplo, el plegamiento de una pequeña proteína, una horquilla β-, puede entenderse a nivel mundial en términos de los estados se muestra en la Figura 1. A pesar de que se trata de comprender el plegamiento de la proteína en cada simplista esta forma, el actual estado de la técnica está muy lejos de este objetivo.

En cada etapa del proceso de simulación, una configuración de la proteína solvated puede reconstruirse. Sin embargo, la simulación puede ser llevada a microsegundos de nanosegundos en unidades de femtoseconds (10 -15), por lo que el número de este tipo de configuraciones intermedias podrían ser fácilmente millones en número. Por lo tanto, la tarea consiste en identificar y capturar representante configuraciones intermedias. Puesto de trabajo en la estructura espacial de la proteína es extremadamente compleja, a menudo los investigadores identificar algunos rasgos característicos fundamentales de la proteína o, a menudo, los llamados coordenadas de reacción, y el estudio de las tendencias y variaciones en estas coordenadas de reacción [21, 23].

En este trabajo se utilizará un proceso de cuatro pasos hacia la comprensión de plegado de una proteína (Figura 2]. El primer paso consiste en la simulación in silico que da lugar a una gran colección de datos de puntos, cada punto es un conjunto de los elementos característicos del plegamiento de proteínas en ese momento. Por ejemplo, el radio de gyration o el número de bonos de hidrógeno podría ser tales características. En los Resultados / Discusión sección, el estudio de β-horquilla plegable como un espectáculo caso y describir siete de esos rasgos característicos que hemos utilizado anteriormente en el estudio de esta proteína.

En el segundo paso, se estudian estos puntos de datos para extraer el conjunto de rasgos característicos que llamamos patrón de clusters. Una vez más, en el caso de la horquilla β-, los datos son puntos de siete dimensiones, que corresponden a los elementos característicos de la proteína en cada intervalo de tiempo (véase el cuadro 1 para una pequeña porción de los datos como un ejemplo). En el tercer paso, estos patrones se filtran a retener los más significativos. Es muy difícil para el modelo de patrones significativos en este ámbito, por lo que se han combinado la segunda y tercera etapas y el uso de parámetros adecuados para filtrar las pautas posiblemente insignificante: utilización de la categoría de tamaño (en términos de filas) y la Z de la.

El cuarto paso es analizar los patrones de uso. Esto implica la extracción de la estructura de la configuración usando las coordenadas del tiempo y el estudio de la correlación de las distintas estructuras. Por ejemplo, se puede observar que el núcleo hidrofóbico está formado antes de la β-strand hidrógeno bonos, o viceversa, y se puede interconectar distintos estados de energía libre en diferentes superficies de energía libre de la vigilancia de la alta dimensión (multi-columna) los patrones de uso. Estos hallazgos pueden proporcionar una mejor comprensión del mecanismo de plegado de proteínas. Además, el tiempo de correlación entre los diversos patrones o estados pudieran ser estudiados. Por ejemplo, es muy útil saber qué patrón o el estado precede a la otra y por cuánto tiempo.

A continuación, describimos en detalle los pasos segundo y tercero en nuestro enfoque, como se muestra en la Figura 2. Estamos modelo de la extracción problema como una combinatoria de detección de problema durante al menos tres razones: (1) Los datos se obtienen a partir de una réplica de cambio dinámica molecular (REMD) método [24] (más detalles a continuación). Este método es esencialmente un método de Monte Carlo, por lo que la serie temporal no es estrictamente en tiempo real debido al azar Monte Carlo proceso de intercambio. Además, nuestro interés es en la búsqueda de patrón de los grupos que no están necesariamente correlacionados en el tiempo. (2) Esto hace hincapié en que cualquier probabilístico (o no-determinista) componente puede ser aislado del algoritmo y el problema. Cualquier ruido de alta frecuencia pueden ser resueltas en gran medida a través de una introducción de una función de δ (véase más adelante). (3) El patrón de la firma de la agrupación ayuda a interpretar los grupos con bastante facilidad. Además, en comparación con la simple agrupación de los algoritmos de agrupación o en publicaciones anteriores [21, 25], este proporciona un completo y eficiente (en tiempo lineal) método para encontrar las pautas de la firma. Cabe señalar que esta es la fundamental razón por la que eligió usar este método, ya que nos permite tener un mayor control sobre un grupo aceptable que también es significativa en términos del proceso de doblado.

Un pequeño pero importante de proteínas del sistema ha sido seleccionada como un ejemplo para demostrar nuestro enfoque para comprender el proceso de doblado. Esta es una pequeña proteína de 16 residuos de β-horquilla (GEWTYDDATKTFTVTE) de la C-terminal de la proteína G (41-56 de residuos archivo 2gb1.pdb AP). Su mecanismo de plegado y doblado energía libre estados han sido estudiados ampliamente en trabajos anteriores [21, 23]. El actual estudio se utilice nuestro nuevo enfoque para el análisis de las actuales trayectorias de las anteriores simulaciones en REMD explícita disolvente [21, 24]. REMD El método de dinámica molecular trayectorias parejas con una temperatura de intercambio de Monte Carlo proceso eficiente para la toma de muestras de la conformación del espacio. En este método, las réplicas se ejecutan en paralelo en una secuencia de temperaturas que van desde la temperatura deseada a una alta temperatura a la que la réplica puede fácilmente superar las barreras de energía. De vez en cuando, las configuraciones de vecinos réplicas se intercambian y que el intercambio es aceptado por un Metropolis criterio de aceptación que garantice el equilibrio detallado. Debido a la alta temperatura réplica puede atravesar las barreras de alta energía, esto proporciona un mecanismo para la baja temperatura réplicas para superar la cuasi-ergodicity evitar que se encuentran en una sola réplica de la temperatura.

Esta horquilla β-ha recibido mucha atención recientemente de los dos frentes teóricas y experimentales [11, 13, 14, 18, 20, 26 - 30]. Las hojas y β-α-hélices son las principales estructuras secundarias en proteínas. Se cree que la comprensión de plegado de estos elementos será la base para la investigación de más grandes y más complejas estructuras. El estudio aislado de las hojas de β-desde hace tiempo, han visto limitadas por la falta de un sistema experimental prestan. El avance de los experimentos [11] Serrano y Eaton [13] Recientemente, ha creado grupos de esta horquilla β-como el sistema de elección para estudiar β-hojas en el aislamiento. Estos experimentos pioneros inspirado una serie de trabajos teóricos sobre este sistema con diversos modelos [18, 20, 21, 26, 27, 31, 32]. Sin embargo, aún hay un número importante de aspectos que siguen siendo controvertidos, tales como la importancia relativa y el tiempo-el orden entre la β-filamento de hidrógeno y la formación de los bonos núcleo hidrofóbico formación, y la existencia de α-helicoidal intermedias durante el plegado.

Parámetros de simulación

En este estudio, un modelo de átomo-El Optimizado Posibilidades de Liquid Simulations-Todos-Atom campo de fuerza [33] con un modelo explícito de disolvente, simple Encargado de Centros de modelo [34]-se utiliza para la descripción de la proteína en el agua solvated . Un total de 64 réplicas de la solvated sistema que consta de 4342 átomos se simula con temperaturas de 270 K, que abarca a 695 K. Para cada réplica, de 3 nanosegundo simulación dinámica molecular se ejecuta con réplicas de cada 400 intentos de los intercambios femtoseconds. El lector puede referirse a [21, 23] para más detalles de esta simulación. Por cada conformación, siete se usan las coordenadas de reacción (Tabla 1]. Hay un total de aproximadamente 20000 conformaciones guardado para cada réplica. Tabla 1 recoge una pequeña parte de los datos de la réplica en 310 K, que es la temperatura biológica.

Estas simulaciones han revelado un núcleo hidrofóbico impulsado mecanismo de plegado de energía libre mapa de análisis [21]. Dado que se trata de un sistema bien estudiado y una gran cantidad de datos disponibles, las comparaciones con otras herramientas de análisis, tales como la energía libre mapa de análisis, podría ser más fácil y más sencillo. Diversas reacciones obtenidas de las coordenadas anteriores sirven como punto de partida.

Discovery Parámetros

A pesar de que el marco desarrollado para una función δ muy general, en aras de la simplicidad, en esta sección tratamos δ (x) a ser una constante función. Así, δ (x) = c para algunos constante Para cada x. El δ funciones para cada columna de la Tabla 1 se presenta de la siguiente manera: δ 1 (x) = 0,2, δ 2 (x) = 0,6, δ 3 (x) = 0,35, δ 4 (x) = 0,15, δ 5 (x ) = 5,0, δ 6 (x) = 16,5, δ 7 (x) = 1,0 x para todos. Además, el quórum k se define como 2000. Cuadro 2 se enumeran algunas representante de los patrones de tamaño dos con estos parámetros. El tiempo no se muestran secuencias debido a las limitaciones de espacio. Estas sencillas pautas se pueden comparar directamente con los anteriores estados de energía libre en las tres dimensiones de energía libre mapas de contorno. Estas son tres dimensiones de las parcelas libres de energía frente a un par de coordenadas de reacción o de las columnas de datos de la Tabla 1.

Uno podría menudo quieren estudio detallado de los patrones o estructuras predefinidas algunas subregiones, como las estructuras se desarrolló en el conjunto. Más evidencia ha demostrado que la proteína se desarrolló en las estructuras de los estados no están completamente extendido, pero a menudo tienen estructuras bien definidas en lugar [35]. Esto también puede evitar el problema de que en estas pautas importantes zonas menos pobladas, se pasa por alto debido a la menor población que el quórum k predefinidas. Así, algunos menos poblada libre de energía en los estados de energía libre paisajes pueden ser recuperados mediante la reducción del quórum. Por lo tanto, otra serie de parámetros se han utilizado, y aquí estamos limitar nuestra búsqueda de puntos de datos con Y 5,0 Å (véase el cuadro 1 para las definiciones de estas coordenadas de reacción), con k = 100. Sin embargo, otro conjunto de parámetros han incluido Y 9,0 Å con k = 50. Un subconjunto de los resultados se muestra más adelante. Por lo tanto, este enfoque podría ser de utilidad para las búsquedas patrón jerárquico que poco a poco el zoom en subconjuntos de datos predefinidos.

Análisis de los resultados

Para obtener una estructura de representante (s) de un conjunto de configuraciones c i, el conjunto está dividida en un número mínimo de grupos G j tal que para cada G j existe un representante , Y para cada uno La estructura correspondiente a c k es en la mayoría de 1 Å de RMSD . Así, cada G j será representado por una estructura que corresponde a [21, 26].

Conclusión

En este trabajo, hemos presentado un método para mejorar nuestra comprensión de los mecanismos de plegamiento de proteínas. En el centro de este método es una combinatoria patrón de descubrimiento algoritmo que analiza las múltiples dimensiones de datos de la simulación de la trayectoria de plegado de proteínas. El enfoque se basa en la modalidad de cálculo, cada patrón está definido por un conjunto de coordenadas de la reacción. Un pequeño pero importante de proteínas del sistema, una β-horquilla de la C-terminal de la proteína G, que se utiliza para demostrar este enfoque. Se muestra que el método no sólo se reproducen las anteriormente declaradas exentas de energía en los estados mapas de curvas de energía libre, pero también revela nueva información previamente pasado por alto en la energía libre paisaje análisis acerca de las estructuras intermedias y el mecanismo de plegado. También está demostrado ser útil en la toma de las interconexiones entre las diversas tridimensional de las superficies de energía libre de reacción frente a distintas coordenadas, y también explica el mecanismo detrás del proceso de doblado. El método también valida la elección de las coordenadas de reacción como el análisis sin necesidad de utilizar la energía libre y compara los valores con los que los utilizan. El éxito con β-horquilla es muy alentador, y actualmente estamos estudiando la aplicación de este método a otros más grandes moléculas de proteínas.

Como se dice en la introducción, es importante para estudiar la correlación entre los diversos patrones o estados. Por ejemplo, es muy útil saber qué patrón o el estado precede a la otra y por cuánto tiempo. Por supuesto, esto requiere tiempo real la trayectoria de datos. El actual estudio utiliza los anteriores trayectorias de REMD, que es un método de Monte Carlo, por lo que la secuencia de tiempo en los puntos de datos no es en tiempo real. Tras el éxito de este método con los datos actuales, creemos que seremos capaces de obtener el tiempo de correlación de los patrones, y estamos investigando en la actualidad.

Materiales y Métodos

En primer lugar, definir el problema a la mano y, a continuación, dar un algoritmo de tiempo lineal para resolver el problema. El número de grupos puede ser fácilmente controlada por el uso de un adecuado δ () (véase infra).

Descripción del problema de combinatoria.

En esta sección, se describe el problema de combinatoria. En este sentido, también hacer algunas observaciones que se han simple muy útiles y prácticas (como lineal-δ número de grupos y así sucesivamente). También indican en la medida de las diferentes funciones (tales como la forma de δ ()) puede ser relajada sin sacrificar el marco general presentado en esta sección. Un lector puede saltar las declaraciones y las pruebas de estas observaciones, sin pérdida de continuidad. Definiciones 1 y 2 de identificar el patrón de descubrimiento o de la agrupación problema se utiliza en este documento, y los resultados / Discusión sección describe un producto sensible al algoritmo a descubrirlos.

En primer lugar, comenzar con una definición general de la agrupación y δ-δ () y también las condiciones en las que la cantidad de patrones que son pequeños.

Definición 1. (Δ-grupo, el grupo máximo δ) Dado δ (): RR +, , 1 ≤ in y k quórum. Un cluster es δ-i con la recogida de , Tal que si , Y luego . Además, V c es máxima si no existe V tal que c Y V c es un δ-cluster.

Aunque el uso general δ () abre la posibilidad de diversos pre-procesamiento de los datos, es importante identificar una razonable δ (). Nos imponen la siguiente condición en δ (), llamándola la limitada función δ. Habida cuenta de tres elementos de datos con ν 1 2 3, si (v 3 - δ (v 3))(1 + δ v (v 1)), (v 2 - δ (v 2))(v 3 - δ (v 3)) y (v 2 + δ (v, 2))(1 + δ v (v 1)).

Esta es una condición razonable, en un aceptable δ (), como puede verse en la consecuencia de la limitación impuesta en Lemma 1. Una multitud de funciones continuas satisfacer esta condición, y en el resto del documento se asume que δ () usamos también cumple esta condición.

Lemma 1. A-δ ν en el grupo 1 2 <… ν n

Es de la forma ν i <ν i +1,…, i + l ν.

Vamos V-δ ser un grupo con ν min i) como mínimo y ν max i + l), como la máxima elementos. Desde ν ν min max y están en el grupo δ-, ν max - δ (ν max)ν min + δ (ν min). Por lo tanto, para cualquier , Impuestas por el estado, entonces ν i - δ (ν i) ≥ ν max - δ (ν max) y ν i - δ (ν i) ≤ ν min + δ (ν min):

Por lo tanto, la contención de los intervalos es como se muestra, por lo tanto, para cada i ν, ν mini max, - Cluster.

Lemma 2. El número máximo de grupos δ-no es más que n donde δ () se ve limitada.

Por Lemma 1, cualquier δ-cluster es un intervalo (contiguo elementos ordenados en la lista) ordenados en la lista de elementos de datos. Vamos a demostrar que cualquiera de los dos intervalos que corresponden a dos grupos-δ máxima no puede ser tal que una figura en la otra. Supongamos al contrario que uno está contenido en el otro. Evidentemente, en la definición de maximality, el más pequeño intervalo no es máxima, dando lugar a una contradicción. Como no figura en el intervalo de la otra, es posible asignar un elemento único en la ordenada elementos de datos para cada intervalo. Así, el número de intervalos no puede superar el número de elementos de datos, de ahí el resultado.

Corolario 1. Si δ (x) = c para algunos , Entonces el número de agrupaciones δ-no es más que n.

El bicluster tiene en cuenta las diferentes características de las columnas o en los datos: la definición natural de ese grupo, se indica a continuación.

Definición 2. (Bicluster, máxima bicluster) Dado δ j (): RR +, k quórum y , 1 ≤ j ≤ m, 1 ≤ n ≤ i. Una colección bicluster es con i y j Tal que para cada j, Es un grupo j-δ. Además, V c es máxima si no existe adicionales i 'o j' con los correspondientes V con c C tal que V es un bicluster.

Para facilitar la consulta, la bicluster también se llama un patrón de la categoría, ya que un grupo puede ser representado por el patrón de la firma (J 1 = c 1, J 2 = c 2 ,..., J L = c L), donde , 1 ≤ k ≤ L. Estas J 1, 2 ,..., J J L representan diversos reacción coordenadas de la trayectoria de plegado de proteínas (que se muestra en el Cuadro 1]. Esta representación es más adecuada para la interpretación de los resultados, como se ha visto en otras secciones de este documento. El tamaño de la bicluster es L, y k es el número de ocurrencias o quórum de la agrupación.

Lemma 3. Los siguientes son consecuencia de la limitación maximality: (1) Si una colección de i es tal que V donde c es una máxima δ-cluster para algunos j, entonces no existe ningún otro grupo máxima δ-V c cV tal que . (2) Si una colección de j es tal que V donde c es una máxima δ-cluster para algunos j, entonces no existe ningún otro grupo máxima δ-V c cV tal que .

Lemma 4. Dado , 1 ≤ jm, 1 ≤ ni. El número máximo de biclusters no es más que n 2 m.

En un máximo bicluster V c para algunos j, No es necesariamente las mejores. El número de esos grupos por Lemma 2 no puede ser más que n 2. Por Lemma 3, el presente sólo puede pertenecer a un máximo bicluster. Por lo tanto, no puede haber más de 2 m n biclusters máxima, ya que hay m columnas.

El algoritmo de tiempo lineal.

Descripciones similares de detección bicluster aparecen en [36], en la que los autores presentan sólo una vez empírica obligado (lineal con el tamaño de salida). G. Alexe PL Hammer y también presentar un algoritmo de tiempo polinomial incremental con un total de tiempo de funcionamiento de O (Nnm 2) (comunicación personal). N es el número de patrones en la salida, y (n × m) es el tamaño de la De entrada. En esta sección, se presenta un producto sensible a todos algoritmo que calcula la máxima biclusters. El algoritmo tiene dos pasos principales. En el primer paso, la máxima δ-se calculan las agrupaciones, y en el segundo paso, la máxima biclusters se calculan utilizando los grupos de la primera etapa.

Paso 1: máxima δ j-cluster de computación. Para cada j, 1 ≤ jm, calcular la máxima δ j-cluster, . Para simplificar, que el número de estos se L j y los grupos temáticos que se , 1 ≤ ≤ l y L j que se calcula como se describe a continuación. Presentamos un simple algoritmo que hace un barrido lineal ordenados de las entradas para cada v ij j fijo utilizando dos punteros y l i: i pistas del comienzo de la agrupación, y pistas de l final de la agrupación. El fin puntero se incrementa hasta que ya no es un grupo que cumpla los δ (), y sólo entonces comenzar el puntero se incrementa. El pseudocódigo, Compute Cluster-(), describe la máxima δ-cluster cálculos, para cada j. Para evitar el desorden, el fin de comprobar la entrada no está incluida en el código.

- Compute Cluster ()

(1) Ordenar la ν i 's para obtener ν 1, ν 2,…, n ν

(2) i ← 1, li + 1

(3) Si

(4) Luego ll + 1, ir al paso (3)

(5) Else ,

Ii + 1, ir al paso (3)

Luego, para cada ν ij, 1 ≤ ni, j 1 ≤ ≤ m, un conjunto de agrupaciones δ-v 'ij se calcula de la siguiente manera:

Paso 2: máxima bicluster cómputo. El algoritmo en este paso se basa en el conjunto intersección problema descrito anteriormente [37] en el contexto de la computación redundantes motivos de irredundant. El algoritmo funciona en v 'ij, 1 ≤ ni, j 1 ≤ ≤ m, de la última etapa.

Se describe un simple algoritmo recursivo para resolver este problema. Este algoritmo implícitamente construye un árbol en un primer fondo de manera que (1) cada nivel corresponde a un j, por lo tanto, la altura del árbol es m, y (2) de cada nodo no hoja en el nivel l corresponde a j = ( -- L) (la raíz en el nivel 0 corresponde a la (j = m), y tiene a la mayoría (L j + 1) los niños, el niño ℓ ª, , Corresponde al grupo δ - Y el último niño ([L j + 1] ª infantil) hace caso omiso de la Δ-grupos. El algoritmo es eficiente debido a los dos factores siguientes: (1) el uso de una estructura de datos (D en el pseudocódigo a continuación) para almacenar la máxima biclusters, a fin de que la búsqueda de una forma arbitraria que se puede hacer rápidamente, y (2) que ponga fin al Árbol de recorrido de manera adecuada. La estructura de datos para su uso sugerido es un árbol de manera que cada consulta tiene log n tiempo. La condición de terminación (línea [2,4] de la pseudocódigo) es tal que cada nodo hoja corresponde a la máxima bicluster ya sea definida por el δ-clusters (función de los valores) Donde j 1j 2 j…p o sus variantes de la forma Donde q 1 ≤ ≤ ρ.

El pseudocódigo de la rutina recursiva Generar-Set () se muestra a continuación, se describe el algoritmo. Asumir una función Add-set (R, C), que se inserta R, un subconjunto de los enteros entre uno y n, en un árbol de la estructura de datos D, junto con el juego C: entonces una consulta de la forma, si existe un conjunto R D toma en O (log n) tiempo. La convocatoria inicial es Generar-Set ((1,2,…, n), φ, m)).

Generar-Set (R, C, j)

(1) Si (j ≤ 0) entonces la salida

(2) Para

Vamos

Vamos

Si Existe en D (como (R ", C")), añadir A la C "

Else

Añadir-set ( ) A D

Generar-Set (

(3) Generar-Set (R, C, j - 1)

El nivel máximo se biclusters , Calculada para cada uno (R, C) almacenados en D.

Análisis del algoritmo.

En primer lugar, demostrar que el algoritmo es correcto en la computación todos los biclusters máximo y demostrar que el siguiente algoritmo se ejecuta en tiempo lineal con el tamaño de la salida.

Corrección de la Algoritmo. En primer lugar, muestran que cada computarizada (R, C) es una bicluster. De la construcción, para cada j, Δ-es un grupo. Así, (R, C) es una bicluster. Luego, tenemos que demostrar que es el máximo. Supongamos que no es. Luego existe v tal que ij Es un bicluster. De ahí que para cada j, Δ-es un grupo. Luego, en la subrutina llamada Generar-Set (R, C, i '), de la pseudocódigo, este conjunto debe haber sido creado, conduce a una contradicción. Por lo tanto, la presunción es errónea.

Luego, existe asumir Tal que Es un bicluster. De ahí que para cada j, Δ-es un grupo. Luego en el paso 3 de la subrutina llamada Generar-Set (R, C, i), correspondiente a la V d j 'debe haber sido incluido, dando lugar a una contradicción. Por lo tanto, la presunción es errónea. Así, todos los conjuntos son computados máxima biclusters. Por similares argumentos, es fácil ver que si hay alguna bicluster máxima definida en el conjunto de datos, hay una de las computa R R's.

De la complejidad del algoritmo. Asumir la entrada de elementos se ν ij, 1 ≤ ni, j 1 ≤ ≤ m. Considerar el primer paso de la computación-δ grupos para cada j. La clasificación de los elementos ν i, 1 ≤ n ≤ I toma O (n log n) tiempo. El algoritmo funciona mediante el escaneo de la entrada de izquierda a derecha, a decir i I + s, donde el conjunto (i ν, ν i + 1,…, i + ν s) es una máxima δ-cluster. Luego, la entrada es de escaneado de i + 1, i + s + 1, i + s + 2, en adelante… y así sucesivamente. Así, cada elemento de datos es visitado no más de dos veces. Suponiendo que la comparación puede hacerse constante en el tiempo, este paso del algoritmo toma O (n log n + n) = O (n log n) tiempo para cada j.

A continuación, examinar el segundo paso de la computación máxima biclusters. Aviso de que la búsqueda en el paso (2,4), de la Genera-Set subrutina que se puede hacer log n en el tiempo. En la llamada recursiva-estructura de árbol (de la subrutina Generar-Set), cada nodo hoja corresponde a una máxima bicluster. En un árbol, el número de nodos internos está limitada por el número de nodos hoja y cada nodo hoja es sólo golpeó tantas veces como el número de elementos en cada patrón, por lo tanto, suponiendo que el tamaño de salida es N (el número total de elementos en Todos la máxima biclusters) y en el segundo paso del algoritmo toma O (N log n) tiempo. Así, el tiempo dedicado por completo el algoritmo es O ((nm + N) log n), donde N es el tamaño de la producción y nm es el tamaño de la entrada.

Agradecemos a Jiawu Feng, quien hizo la pronta aplicación del algoritmo. También queremos dar las gracias a Gustavo Stolovitzky, Ajay Royyuru, Isidore Rigoutsos, Jed Pitera, y William Swope útil para muchos debates.