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
iI i , j
I
H ( I , J )   i I , j  J
ei , J
RS i2, j
I J


j J
J
ei , j
eI , J


iI , 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