De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

Biclustering , bloque de la agrupación , [1] [2] co-agrupación , o de dos modo de agrupamiento [3] [4] [5] es una minería de datos técnica que permite simultánea de agrupamiento de las filas y columnas de una matriz . El término fue introducido por primera vez por Boris Mirkin [6] para nombrar una técnica introducida muchos años antes, [6] en 1972, por J. A. Hartigan. [7]

Dado un conjunto de muestras representadas por un vector de características -dimensional, el conjunto de datos completo se puede representar como filas en columnas (es decir, una matriz). El algoritmo de biclustering genera biclusters, un subconjunto de filas que exhiben un comportamiento similar en un subconjunto de columnas, o viceversa.

Desarrollo [ editar ]

Biclustering fue introducido originalmente por JA Hartigan en 1972. [8] El término biclustering fue utilizado más tarde por Mirkin. Este algoritmo no se generalizó hasta 2000 cuando Y. Cheng y GM Church propusieron un algoritmo biclustering basado en la varianza y lo aplicaron a los datos de expresión genética biológica. [9] Su artículo sigue siendo la literatura más importante en el campo de la expresión de genes biclustering.

En 2001 y 2003, IS Dhillon presentó dos algoritmos que aplicaban biclustering a archivos y palabras. Una versión se basó en particiones de gráficos espectrales bipartitos. [10] El otro se basó en la teoría de la información. Dhillon asumió que la pérdida de información mutua durante biclustering era igual a la distancia de Kullback-Leibler ( distancia KL) entre P y Q. P representa la distribución de archivos y palabras características antes de biclustering, mientras que Q es la distribución después de biclustering. La distancia KL sirve para medir la diferencia entre dos distribuciones aleatorias. KL = 0 cuando las dos distribuciones son iguales y KL aumenta a medida que aumenta la diferencia. [11]Por lo tanto, el objetivo del algoritmo era encontrar la distancia KL mínima entre P y Q. En 2004, Arindam Banerjee utilizó una distancia de Bregman ponderada en lugar de la distancia KL para diseñar un algoritmo biclustering que fuera adecuado para cualquier tipo de matriz. a diferencia del algoritmo de distancia KL. [12]

Para agrupar más de dos tipos de objetos, en 2005, Bekkerman expandió la información mutua en el teorema de Dhillon de un solo par a múltiples pares.

Complejidad [ editar ]

La complejidad del problema del bicluster depende de la formulación exacta del problema y, en particular, de la función de mérito utilizada para evaluar la calidad de un bicluster determinado. Sin embargo, las variantes más interesantes de este problema son NP-completo . NP-completo tiene dos condiciones. En el caso simple de que solo haya un elemento a ( i , j ), ya sea 0 o 1 en la matriz binaria A, un biclúster es igual a un biclicuo en el gráfico bipartito correspondiente. El biclúster de tamaño máximo es equivalente al biclúster de borde máximo en un gráfico bipartito. En el caso complejo, el elemento de la matriz A se utiliza para calcular la calidad de un bicluster dado y resolver la versión más restringida del problema. [13]Requiere un gran esfuerzo computacional o el uso de heurísticas con pérdidas para cortocircuitar el cálculo. [14]

Tipo de bicluster [ editar ]

Los diferentes algoritmos de biclustering tienen diferentes definiciones de bicluster. [14]

Ellos son:

  1. Bicluster con valores constantes (a),
  2. Bicluster con valores constantes en las filas (b) o columnas (c),
  3. Bicluster con valores coherentes (d, e).

1.Bicluster con valores constantes

Cuando un algoritmo de biclustering intenta encontrar un bicluster constante, la forma normal de hacerlo es reordenar las filas y columnas de la matriz para que pueda agrupar filas / columnas similares y encontrar biclusters con valores similares. Este método está bien cuando los datos están ordenados. Pero como los datos pueden ser ruidosos la mayoría de las veces, no pueden satisfacernos. Deben utilizarse métodos más sofisticados. Un bicluster constante perfecto es una matriz (I, J) donde todos los valores a (i, j) son iguales a μ. En datos reales, a (i, j) se puede ver como n (i, j) + μ donde n (i, j) es el ruido. Según el algoritmo de Hartigan, al dividir la matriz de datos original en un conjunto de biclusters, la varianza se utiliza para calcular biclusters constantes. Entonces, un bicluster perfecto es una matriz con varianza cero. También,Para evitar la partición de la matriz de datos en biclusters con solo una fila y una columna, Hartigan asume que hay K biclusters dentro de la matriz de datos. Cuando la matriz de datos se particiona en K biclusters, el algoritmo finaliza.

2.Biclusters con valores constantes en filas o columnas

Este tipo de biclusters no se puede evaluar solo por la variación de sus valores. Para finalizar la identificación, las columnas y las filas deben normalizarse en un primer momento. Hay otros algoritmos que, sin paso de normalización, pueden encontrar biclusters que tienen filas y columnas con diferentes enfoques.

3.Biclusters con valores coherentes

Para biclusters con valores coherentes en filas y columnas, se debe considerar una mejora general sobre los algoritmos para biclusters con valores constantes en filas o columnas. Eso significa que se necesita un algoritmo sofisticado. Este algoritmo puede contener análisis de varianza entre grupos, utilizando covarianza entre filas y columnas. En el teorema de Cheng y Church, un bicluster se define como un subconjunto de filas y columnas con casi la misma puntuación. La puntuación de similitud se utiliza para medir la coherencia de filas y columnas.


a) Bicluster con valores constantes
2.02.02.02.02.0
2.02.02.02.02.0
2.02.02.02.02.0
2.02.02.02.02.0
2.02.02.02.02.0
b) Bicluster con valores constantes en filas
1.01.01.01.01.0
2.02.02.02.02.0
3,03,03,03,03,0
4.04.04.04.04.0
5,05,05,05,05,0
c) Bicluster con valores constantes en columnas
1.02.03,04.05,0
1.02.03,04.05,0
1.02.03,04.05,0
1.02.03,04.05,0
1.02.03,04.05,0
d) Bicluster con valores coherentes (aditivo)
1.04.05,00.01,5
4.07.08.03,04.5
3,06.07.02.03,5
5,08.09.04.05.5
2.05,06.01.02.5
e) Bicluster con valores coherentes (multiplicativo)
1.00,52.00,20,8
2.01.04.00.41,6
3,01,56.00,62.4
4.02.08.00,83.2
5,02.510.01.04.0


La relación entre estos modelos de conglomerados y otros tipos de conglomerados, como el de correlación, se analiza en. [15]

Algoritmos [ editar ]

Hay muchos algoritmos de biclustering desarrollados para bioinformática , que incluyen: agrupación de bloques, CTWC (agrupación bidireccional acoplada), ITWC (agrupación bidireccional interrelacionada), δ-bicluster, δ-pCluster, patrón δ, FLOC, OPC, modelo a cuadros , OPSM (submatrices que preservan el orden), Gibbs, SAMBA (Método estadístico-algorítmico para análisis bicluster), [16] Algoritmo robusto de biclustering (RoBA), Crossing Minimization, [17] cMonkey, [18] PRM, DCC, LEB (Localize y Biclusters de extracto), QUBIC (BIClustering cualitativo), BCCA (Algoritmo de agrupación de bicorrelación) BIMAX, ISA y FABIA (Análisis factorial para la adquisición de Bicluster), [19] runibic, [20]y el método híbrido propuesto recientemente EBIC (biclustering basado en la evolución), [21] que demostró detectar múltiples patrones con una precisión muy alta. Más recientemente, se propone IMMD-CC [22] que se desarrolla sobre la base del concepto iterativo de reducción de la complejidad. IMMD-CC es capaz de identificar centroides de co-clúster a partir de una transformación muy dispersa obtenida mediante discretización iterativa multimodo.

También se han propuesto y utilizado algoritmos de biclustering en otros campos de aplicación bajo los nombres de coclustering, agrupamiento bidimensional y agrupamiento subespacial. [14]

Dada la importancia conocida de descubrir patrones locales en los datos de series de tiempo , las propuestas recientes han abordado el problema de la confusión en el caso específico de los datos de expresión génica de series de tiempo . En este caso, los biclusters interesantes se pueden restringir a aquellos con columnas contiguas . Esta restricción conduce a un problema manejable y permite el desarrollo de algoritmos de enumeración exhaustivos eficientes como CCC-Biclustering [23] y e -CCC-Biclustering. [24] Los patrones aproximados en los algoritmos CCC-Biclustering permiten un número dado de errores, por gen, en relación con un perfil de expresión que representa el patrón de expresión en el bicluster. El algoritmo e-CCC-Biclustering utiliza expresiones aproximadas para encontrar e informar todos los CCC-Biclusters máximos mediante una matriz A discretizada y técnicas de procesamiento de cadenas eficientes.

Estos algoritmos encuentran e informan todos los biclusters máximos con columnas coherentes y contiguas con patrones de expresión perfectos / aproximados, en el tiempo lineal / polinomial que se obtiene manipulando una versión discretizada de la matriz de expresión original en el tamaño de la matriz de expresión génica de series de tiempo utilizando una cadena eficiente técnicas de procesamiento basadas en árboles de sufijos . Estos algoritmos también se aplican para resolver problemas y esbozar el análisis de complejidad computacional.

Algunos algoritmos recientes han intentado incluir soporte adicional para combinar matrices rectangulares en forma de otros tipos de datos , incluido cMonkey.

Existe un debate en curso sobre cómo juzgar los resultados de estos métodos, ya que el biclustering permite la superposición entre grupos y algunos algoritmos permiten la exclusión de columnas / condiciones difíciles de conciliar. No todos los algoritmos disponibles son deterministas y el analista debe prestar atención al grado en que los resultados representan mínimos estables . Debido a que este es un problema de clasificación no supervisado , la falta de un estándar de oro dificulta la detección de errores en los resultados. Un método consiste en utilizar múltiples algoritmos biclustering, con la mayoría o súper mayoría de votación entre ellos para decidir el mejor resultado. Otra forma es analizar la calidad de los patrones de cambio y escala en biclusters.[25] Biclustering se ha utilizado en el dominio de la minería de texto (o clasificación) donde se conoce popularmente como co-clustering. [26] Los corpus de texto se representan enforma vectorial como una matriz D cuyas filas denotan los documentos y cuyas columnas denotan las palabras del diccionario. Los elementos de la matriz D ij denotan la aparición de la palabra j en el documento i.A continuación, se aplican algoritmos de agrupación conjunta para descubrir bloques en D que corresponden a un grupo de documentos (filas) caracterizados por un grupo de palabras (columnas).

La agrupación de pruebas puede resolver el problema de escasez de alta dimensión, lo que significa agrupar texto y palabras al mismo tiempo. Al agrupar texto, debemos pensar no solo en la información de las palabras, sino también en la información de los grupos de palabras compuestos por palabras. Luego, de acuerdo con la similitud de las palabras clave en el texto, eventualmente se agruparán las palabras clave. A esto se le llama agrupación conjunta. Hay dos ventajas de la agrupación conjunta: una es la agrupación de la prueba basada en agrupaciones de palabras que puede reducir en gran medida la dimensión de la agrupación, también puede ser apropiado medir la distancia entre las pruebas. En segundo lugar, se extrae información más útil y se puede obtener la información correspondiente en grupos de prueba y grupos de palabras. Esta información correspondiente se puede utilizar para describir el tipo de textos y palabras, al mismo tiempo,el resultado de la agrupación de palabras también se puede utilizar para la extracción de texto y la recuperación de información.

Se han propuesto varios enfoques basados ​​en el contenido de información de los bloques resultantes: enfoques basados ​​en matrices como SVD y BVD, y enfoques basados ​​en gráficos. Los algoritmos de teoría de la información asignan iterativamente cada fila a un grupo de documentos y cada columna a un grupo de palabras, de modo que la información mutua se maximiza. Los métodos basados ​​en matrices se centran en la descomposición de matrices en bloques de modo que se minimice el error entre la matriz original y las matrices regeneradas de la descomposición. Los métodos basados ​​en gráficos tienden a minimizar los cortes entre los grupos. Dados dos grupos de documentos d 1 y d 2, el número de cortes se puede medir como el número de palabras que aparecen en documentos de los grupos d 1 y d 2 .

Más recientemente (Bisson y Hussain) [26] han propuesto un nuevo enfoque de utilizar la similitud entre palabras y la similitud entre documentos para coagrupar la matriz. Su método (conocido como χ-Sim , por similitud cruzada) se basa en encontrar la similitud documento-documento y la similitud palabra-palabra, y luego usar métodos de agrupamiento clásicos como el agrupamiento jerárquico. En lugar de agrupar explícitamente filas y columnas alternativamente, consideran las apariciones de palabras de orden superior, teniendo en cuenta inherentemente los documentos en los que aparecen. Así, la similitud entre dos palabras se calcula en función de los documentos en los que aparecen y también de los documentos en los que aparecen palabras "similares". La idea aquí es que dos documentos sobre el mismo tema no necesariamente usan el mismo conjunto de palabras para describirlo, sino un subconjunto de palabras y otras palabras similares que son características de ese tema. Este enfoque de tomar similitudes de orden superior toma en consideración la estructura semántica latente de todo el corpus con el resultado de generar una mejor agrupación de documentos y palabras.

En las bases de datos de texto, para una colección de documentos definida por un documento por matriz de términos D (de tamaño m por n, m: número de documentos, n: número de términos), la metodología de agrupación basada en coeficientes de cobertura [27] produce el mismo número de agrupaciones tanto para documentos como para términos (palabras) utilizando un experimento de probabilidad de doble etapa. De acuerdo con el concepto de coeficiente de cobertura, el número de conglomerados también se puede estimar de forma aproximada mediante la siguiente fórmula, donde t es el número de entradas distintas de cero en D. Tenga en cuenta que en D cada fila y cada columna deben contener al menos un elemento distinto de cero.

A diferencia de otros enfoques, FABIA es un modelo multiplicativo que asume distribuciones de señales no gaussianas realistas con colas pesadas . FABIA utiliza técnicas de selección de modelos bien entendidas, como enfoques variacionales, y aplica el marco bayesiano . El marco generativo permite a FABIA determinar el contenido de información de cada bicluster para separar biclusters falsos de biclusters verdaderos.

Ver también [ editar ]

  • Caja de herramientas BIDEAL para biclustering
  • Caja de herramientas MTBA para biclustering
  • Análisis de concepto formal
  • Biclique
  • Conexión de Galois
  • BiclustGUI: paquete R para Biclustering

Referencias [ editar ]

  1. ^ G. Govaert; M. Nadif (2008). "Agrupación de bloques con modelos de mezcla de bernoulli: comparación de diferentes enfoques". Estadística Computacional y Análisis de Datos . 52 (6): 3233–3245. doi : 10.1016 / j.csda.2007.09.007 .
  2. ^ R. Balamurugan; AM Natarajan; K. Premalatha (2015). "Optimización de agujero negro de masa estelar para datos de expresión génica de microarrays biclustering". Inteligencia artificial aplicada . 29 (4): 353–381. doi : 10.1080 / 08839514.2015.1016391 . S2CID 44624424 . 
  3. ^ G. Govaert; M. Nadif (2013). Co-clustering: modelos, algoritmos y aplicaciones . ISTE, Wiley. ISBN 978-1-84821-473-6.
  4. ^ R. Balamurugan; AM Natarajan; K. Premalatha (2016). "Un método de búsqueda de armonía modificado para Biclustering Microarray Gene Expression Data". Revista Internacional de Minería de Datos y Bioinformática . 16 (4): 269-289. doi : 10.1504 / IJDMB.2016.082205 .
  5. ^ Van Mechelen I, Bock HH, De Boeck P (2004). "Métodos de agrupación en clústeres de dos modos: una descripción estructurada". Métodos estadísticos en la investigación médica . 13 (5): 363–94. CiteSeerX 10.1.1.706.4201 . doi : 10.1191 / 0962280204sm373ra . PMID 15516031 . S2CID 19058237 .    
  6. ↑ a b Mirkin, Boris (1996). Clasificación y agrupamiento matemático . Editores académicos de Kluwer. ISBN 978-0-7923-4159-8.
  7. ^ Hartigan JA (1972). "Agrupación directa de una matriz de datos". Revista de la Asociación Estadounidense de Estadística . 67 (337): 123–9. doi : 10.2307 / 2284710 . JSTOR 2284710 .  
  8. ^ Hartigan JA (1972). "Agrupación directa de una matriz de datos". Revista de la Asociación Estadounidense de Estadística . 67 (337): 123–129. doi : 10.1080 / 01621459.1972.10481214 .
  9. ^ https://www.cs.princeton.edu/courses/archive/fall03/cs597F/Articles/biclustering_of_expression_data.pdf Cheng Y, Church G M. Biclustering de datos de expresión [C] // Ismb. 2000, 8: 93-103.
  10. ^ Dhillon I S. Co-agrupamiento de documentos y palabras usando particiones de gráficos espectrales bipartitos [C] // Actas de la séptima conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos. ACM, 2001: 269–274.
  11. ^ Dhillon IS, Mallela S, Modha D S. Co-agrupamiento teórico de la información [C] // Actas de la novena conferencia internacional de ACM SIGKDD sobre descubrimiento de conocimientos y minería de datos de KKluwer Academic Publishersnowledge. ACM, 2003: 89–98.
  12. ^ Banerjee A, Dhillon I, Ghosh J, et al. Un enfoque de máxima entropía generalizada para el co-clustering de Bregman y la aproximación de matrices [C] // Actas de la décima conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos. ACM, 2004: 509–514.
  13. ^ Peeters R (2003). "El problema de máxima biclicua de borde es NP-completo" . Matemáticas aplicadas discretas . 131 (3): 651–654. doi : 10.1016 / S0166-218X (03) 00333-0 .
  14. ↑ a b c Madeira SC, Oliveira AL (2004). "Biclustering algoritmos para análisis de datos biológicos: una encuesta". Transacciones IEEE / ACM sobre biología computacional y bioinformática . 1 (1): 24–45. doi : 10.1109 / TCBB.2004.2 . PMID 17048406 . S2CID 206628783 .  
  15. ^ Kriegel, H.-P .; Kröger, P .; Zimek, A. (marzo de 2009). "Agrupación de datos de alta dimensión: una encuesta sobre agrupación subespacial, agrupación basada en patrones y agrupación de correlación". Transacciones de ACM sobre el descubrimiento de conocimientos a partir de datos . 3 (1): 1–58. doi : 10.1145 / 1497577.1497578 . S2CID 17363900 . 
  16. ↑ Tanay A, Sharan R, Kupiec M, Shamir R (2004). "Revelar la modularidad y la organización en la red molecular de levadura mediante el análisis integrado de datos muy heterogéneos en todo el genoma" . Proc Natl Acad Sci USA . 101 (9): 2981-2986. Código Bib : 2004PNAS..101.2981T . doi : 10.1073 / pnas.0308661100 . PMC 365731 . PMID 14973197 .  
  17. ^ Abdullah, Ahsan; Hussain, Amir (2006). "Una nueva técnica de biclustering basada en la minimización de cruces". Neurocomputación . 69 (16-18): 1882-1896. doi : 10.1016 / j.neucom.2006.02.018 .
  18. ^ Reiss DJ, Baliga NS, Bonneau R (2006). "Biclustering integrado de conjuntos de datos heterogéneos de todo el genoma para la inferencia de redes reguladoras globales" . BMC Bioinformática . 7 : 280-302. doi : 10.1186 / 1471-2105-7-280 . PMC 1502140 . PMID 16749936 .  
  19. ^ Hochreiter S , Bodenhofer U, Heusel M, Mayr A, Mitterecker A, Kasim A, Khamiakova T, Van Sanden S, Lin D, Talloen W, Bijnens L, Gohlmann HWH, Shkedy Z, Clevert DA (2010). "FABIA: análisis factorial para adquisición de bicluster" . Bioinformática . 26 (12): 1520-1527. doi : 10.1093 / bioinformatics / btq227 . PMC 2881408 . PMID 20418340 .  
  20. ↑ Orzechowski P, Pańszczyk A, Huang X, Moore JH (2018). "runibic: un paquete de bioconductores para biclustering basado en filas paralelas de datos de expresión génica" . Bioinformática . 34 (24): 4302–4304. doi : 10.1093 / bioinformatics / bty512 . PMC 6289127 . PMID 29939213 .  
  21. ↑ Orzechowski P, Sipper M, Huang X, Moore JH (2018). "EBIC: un algoritmo biclustering paralelo basado en la evolución para el descubrimiento de patrones" . Bioinformática . 34 (21): 3719–3726. arXiv : 1801.03039 . doi : 10.1093 / bioinformatics / bty401 . PMC 6198864 . PMID 29790909 .  
  22. ^ Fanaee-T H, Thoresen, M (2020). "Discretización iterativa multimodo: aplicaciones al co-clustering". Apuntes de conferencias en Ciencias de la Computación . 12323 : 94-105. doi : 10.1007 / 978-3-030-61527-7_7 . hdl : 10852/82994 . ISBN 978-3-030-61526-0.
  23. ^ Madeira SC, Teixeira MC, Sá-Correia I, Oliveira AL (2010). "Identificación de módulos reguladores en datos de expresión génica de series temporales mediante un algoritmo de biclustering de tiempo lineal". Transacciones IEEE / ACM sobre biología computacional y bioinformática . 1 (7): 153-165. doi : 10.1109 / TCBB.2008.34 . PMID 20150677 . S2CID 7369531 .  
  24. ^ Madeira SC, Oliveira AL (2009). "Un algoritmo de biclustering de tiempo polinomial para encontrar patrones de expresión aproximados en series de tiempo de expresión génica" . Algoritmos de Biología Molecular . 4 (8): 8. doi : 10.1186 / 1748-7188-4-8 . PMC 2709627 . PMID 19497096 .  
  25. ^ Aguilar-Ruiz JS (2005). "Patrones de cambio y escalamiento de datos de expresión génica" . Bioinformática . 21 (10): 3840–3845. doi : 10.1093 / bioinformatics / bti641 . PMID 16144809 . 
  26. ↑ a b Bisson G. y Hussain F. (2008). Chi-Sim: una nueva medida de similitud para la tarea de agrupación conjunta . ICMLA . págs. 211–217. doi : 10.1109 / ICMLA.2008.103 . ISBN 978-0-7695-3495-4. S2CID  15506600 .
  27. ^ Can, F .; Ozkarahan, EA (1990). "Conceptos y efectividad de la metodología de agrupamiento basado en coeficientes de cobertura para bases de datos de texto" (PDF) . Transacciones ACM en sistemas de bases de datos . 15 (4): 483–517. doi : 10.1145 / 99935.99938 . hdl : 2374.MIA / 246 . S2CID 14309214 .  

Otros [ editar ]

  • NK Verma, S. Bajpai, A. Singh, A. Nagrare, S. Meena, Yan Cui, "A Comparison of Biclustering Algorithms" en la conferencia internacional sobre sistemas en medicina y biología (ICSMB 2010) en IIT Kharagpur India, págs.90 –97, 16-18 de diciembre.
  • J. Gupta, S. Singh y NK Verma "MTBA: MATLAB Toolbox for Biclustering Analysis", IEEE Workshop on Computational Intelligence: Theories, Applications and Future Directions ", IIT Kanpur India, págs. 148-152, julio de 2013.
  • A. Tanay. R. Sharan y R. Shamir, "Biclustering Algorithms: A Survey", en Handbook of Computational Molecular Biology , editado por Srinivas Aluru , Chapman (2004)
  • Kluger Y, Basri R, Chang JT, Gerstein MB (2003). "Biclustering espectral de datos de microarrays: condiciones y genes de coclustering" . Investigación del genoma . 13 (4): 703–716. doi : 10.1101 / gr.648603 . PMC  430175 . PMID  12671006 .
  • Adetayo Kasim, Ziv Shkedy, Sebastian Kaiser, Sepp Hochreiter, Willem Talloen (2016), Métodos aplicados de biclustering para datos grandes y de alta dimensión con R, Chapman & Hall / CRC Press
  • Orzechowski, P., Sipper, M., Huang, X. y Moore, JH (2018). EBIC: un algoritmo de biclustering paralelo basado en la evolución para el descubrimiento de patrones. Bioinformática .

Enlaces externos [ editar ]

  • FABIA: Análisis factorial para la adquisición de Bicluster, un paquete R —software