Arthur Gonçalves – agc Christian Diego – cdad Icamaan Viegas – ibvs Recife, 18 de Dezembro de 2007 Introdução Clustering Biclustering Algoritmo de Cheng e Church Coupled Two-way Clustering Algoritmo Interative Signature Conclusão Gene Expression Profiling se estabeleceu na última década como técnica padrão para obter impressão digital de tecidos ou células em diferentes condições biológicas Baseado na disponibilidade de sequências inteira de genoma, a tecnologia de microarray permite a medida, simultaneamente, de níveis de mRNA para milhares de genes Gene Expression Profiling são poderosas fontes de informações e tem revolucionado o modo como são estudadas e compreendidas funções em um sistema biológico Dado um conjunto de perfis de expressões gênicas, organizadas juntas como uma matriz com linhas correspondente a genes e colunas correspondendo a condições Agrupar condições e genes em subconjuntos que conduzem a um significado biológico, é uma tarefa conhecida como clustering Dentro de cada cluster os vetores de atributos são similares enquanto vetores de clusters disjuntos são dissimilares Analises via clustering fazem muitas suposições a priori que podem não ser perfeitamente adequadas em todas as circunstancias Clustering devem ser aplicados EXCLUSIVAMENTE a genes ou amostras, implicitamente, direcionando a analise a um particular aspecto do sistema Algoritmos de clustering geralmente procuram agrupar o conjunto de elementos em grupos disjuntos, exigindo que nenhum gene ou amostra pertença a mais que um grupo Bicluster é definido como uma submatriz "amarrada" a um conjunto de genes e um conjunto de amostras Podemos caracterizar um fenômeno biológico por uma coleção de biclusters, cada um representando um diferente tipo de comportamento, ligando um conjunto de genes a um correspondente conjunto de amostra A falta de restrições estruturais em soluções de biclustering permite maior liberdade mas é conseqüentemente mais vulnerável a overfitting Em aplicações clínicas, análise de expressões gênicas é feita em tecidos de pacientes com uma condição médica Usando tais análises, biólogos tem identificado impressões digitais moleculares que podem ajudar na classificação e diagnóstico do status do paciente e guia protocolos de tratamento Um importante aspecto de dados de expressão gênica é seu alto nível de ruídos Microarrays provêem apenas uma rude aproximação de níveis de expressão, e são sujeitos a erros de até 2x o valor mensurado Cheng e Church foram os primeiros a introduzir biclustering para análise de expressão gênica Seu framework representa o problema de biclustering como um problema de otimização, definindo um score para cada bicluster candidato e desenvolvendo heurísticas para resolver o problema de otimização das restrições As restrições forçam a uniformidade da matriz, o procedimento dá preferência a sub-matrizes maiores e a heurística é um algoritmo guloso Cheng e Church implicitamente assumem que pares (gene, condição) em um “bom” bicluster tem um nível de expressão constante, além de possivelmente linhas aditivas e efeitos específicos de colunas Após remover as médias de linhas, colunas e submatrizes o nível residual deverá ser tão pequeno quanto possível Mais formalmente Dado a matriz de expressão gênica E Um subconjunto de genes I Um subconjunto de condições J Nós definimos eI , j e iI i , j I H ( I , J ) i I , j J ei , J RS i2, j I J j J J ei , j eI , J iI , j J ei , j I J RSI , J (i, j) ei, j eI , j ei, J eI , J A intuição por trás dessa definição pode ser compreendida por um exemplo Uma matriz completamente uniforme terá score Zero Dada a definição de score o problema de máximo bicluster procura um bicluster de tamanho máximo entre todos os biclusters com score não excedendo um determinado limiar O tamanho pode ser definido de muitos modos, por exemplo o numero de células na matriz ou o numero de linhas mais o número de colunas O problema de máximo bicluster é NP-Hard se nós forçarmos todas as soluções a serem matrizes quadradas ou se nós usarmos o número total de células da sub-matriz como nosso objetivo de otimização Cheng e Church sugeriram uma heurística gulosa para rapidamente convergir para uma sub-matriz máxima local com score menor que o limiar A idéia é que linhas/colunas com alta contribuição para o score possam ser removidas com garantias de melhoramento no total do score residual médio quadrado Uma possível variação dessa heurística remove todas as linhas e colunas com uma contribuição, para o score residual, maior que um limiar Ao fim, o algoritmo retorna uma sub-matriz com baixo resíduo médio e tamanho máximo local Para descobrir mais que um bicluster foi utilizado o algoritmo de bicluster em matrizes modificadas A modificação inclui randomização dos valores nas células dos biclusters descobertos anteriormente Isto tem o efeito de eliminar a identificação do bicluster com significantes sobreposições Coupled two-way clustering (CTWC), introduzido por Getz, Levine e Domany, define um esquema genérico para transformar um algoritmo de cluster unidimensional (padrão) em um algoritmo de biclustering O algoritmo se basea em ter um algoritmo de cluster unidimensional que possa descobrir clusters significantes (estáveis) A implementação garante que cada par de subconjunto não é encontrado mais que uma vez Note que o procedimento evita a consideracao de subconjuntos com todas as linhas ou colunas, começando de um conjunto de linhas estabelecido quando estiver formando subclusters de subconjuntos de colunas estabelecidos O sucesso da estratégia CTWC depende da performance do dado algoritmo de clustering unidimensional Muitos algoritmos populares, K-means, Hierárquico, não podem ser acoplados ao CTWC, devido a não distinguirem clusters significantes imediatamente de clusters não significantes e/ou fazerem suposição a priori do numero de clusters Getz et al. reportou bons resultados usando o algoritmo SPC hierárquico Cada cluster de genes (condição) estável é gerado dado um subconjunto de condições (resp. gene) Esta relação hierárquica é importante quando tentamos entender o contexto do comportamento de genes ou condições comuns No algoritmo de assinatura iterativa (ISA) a noção de um bicluster significante é definido intrinsecamente nos genes e exemplos do bicluster A intuição é que genes num bicluster são co-regulados e, então, para cada exemplo (gene) a expressão gênica média sobre todos os genes (resp. exemplos) do bicluster deveria ser surpreendente (usualmente alta ou baixa) O ISA converge para um ponto fixo e aproximado que é considerado um bicluster O ponto fixo depende do conjunto inicial Vin e dos limiares TC e TG Para gerar um conjunto representativo de biclusters, pode-se executar o ISA com várias condições iniciais, incluindo conjuntos conhecidos de genes associados ou conjuntos aleatórios Depois de limitar redundâncias (pontos fixos repetidos), o conjunto de pontos fixos pode ser analisado como um conjunto de biclusters O ISA pode ser generalizado atribuindo pesos para cada gene/exemplo de forma que genes/exemplos com comportamento significativo terão maior peso Substituindo as médias simples por médias ponderadas, e o algoritmo pode ser representado utilizando operações matriciais BicAT: http://www.tik.ee.ethz.ch/sop/bicat/ Há uma infinidade de algoritmos para biclustering A escolha dos 3 algoritmos apresentados se baseou nos métodos mais práticos segundo [1] Enquanto clustering restringe a análise a um aspecto particular, biclustering tem um alto poder de representação [1] Livro Texto, capítulo 26 – Biclustering Algorithms: A Survey [2] Dissertação de Mestrado – Daniele Sunaga [3] http://arep.med.harvard.edu/biclustering [4] http://ctwc.weizmann.ac.il [5] http://barkai-serv.weizmann.ac.il/GroupPage Arthur Gonçalves – agc Christian Diego – cdad Icamaan Viegas – ibvs Recife, 18 de Dezembro de 2007
Download
