Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Análise de Grafos em Bioinformática-Aula Introdutória

No description
by

Valdete Almeida

on 20 October 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Análise de Grafos em Bioinformática-Aula Introdutória

Tópicos Especiais em Ciência da Computação
Valdete M. G. de Almeida
valdete@dcc.ufmg.br
O que podemos modelar por meio de grafos?
Redes Tecnológicas:
A internet
Energia elétrica
Linhas metrô
Mapas rodoviários e hidrográficos
Redes Sociais:
Facebook
Myspace
Twitter
Redes de Informações:
Páginas de um site corporativo
Citações de um paper
Redes P2P
Redes Biológicas:
Redes metabólicas
Interações proteicas
Regulação genética
Redes neuronais
Cadeias alimentares
Internet
Sistema de Metrô
Mapa Hidrográfico
Bacia hidrográfica do rio Hérault (sul da França)
Sistema de metrô de Londres
Estrutura da Internet da universidade de San Diego/California
Redes sociais (Facebook)
Crime Organizado
Contatos sexuais
Site corporativo
Mapa metabólico
Enovelamento proteico
Etanol
Interações proteicas (levedura)
Por que estudar grafos/redes?
Aula Introdutória
Análise de Grafos em Bioinformática
Identificar a habilidade de comunicação entre duas entidades em uma rede

Investigar como a estrutura de uma rede restringe a comunicação (ou o movimento) entre os entidades dessa rede

Criar heurísticas ótimas/sub-rotinas para realizar busca de padrões em redes reais
O que são grafos?
Um grafo é definido formalmente como G = (V, E)

Conjunto de vértices (entidades) conectados por arestas (relacionamento)
Redes Tecnológicas
Análise de redes Biológicas
Trabalhos recentes
Redes de Interações de proteínas (PPI)
São interações entre proteínas com a finalidade de desempenhar alguma função biológica (replicação de DNA)

São chamados de interatoma
Zhan-Chao Li, et al. Identication of human protein complexes from local sub-graphs of protein-protein interaction network based on random forest with topological structure features. Anal Chim Acta, 718:32 - 41, March 2012.
Base de dados CORUM

Identificação de PPIs densamente conectadas (humanos)

Predição e cofirmação com base no GO - redes associadas a doenças
Ementa e Cronograma
Cronograma
Ementa
Redes de Interações Ecológicas
Interações entre espécies (redes na ecologia)

Ajuda os pesquisadores a entender e predizer a dinâmica organizacional dos ecosistemas
Miguel Lurgi and David Robertson. Automated experimentation in ecological networks. Autom Exp, 3(1):1, 2011
Descreve tipos de redes ecológicas

Redes de cooperação entre as espécies (mutualismo)

Grafo Bipartido
Descreve tipos de redes ecológicas
Redes de cooperação entre as espécies (mutualismo)
Grafo Bipartido
Referências Bibliográficas
Redes de Interações Atômicas
Interações atômicas proteicas

Ajuda a entender e predizer contatos entre átomos (hidrofóbicos ou polares)
Análise de redes Biológicas
Trabalhos do Nosso Grupo de Bioinformática Estrutural
V M Gonçalves-Almeida, D E V Pires, R C de Melo-Minardi, C H da Silveira, W Meira, and M M Santoro. Hydropace: understanding and predicting cross-inhibition in serine proteases through hydrophobic patch centroids. Bioinformatics, 28(3):342–9, February 2012.
Identificar regiões hidrofóbicas na interface em complexos proteicos

Busca por componentes conexos

Padrões frequentes em casos de inibição cruzada
Identificar regiões hidrofóbicas na interface em complexos proteicos
Busca por componentes conexos
Padrões frequentes em casos de inibição cruzada
Tripsina
Subtilisina
D E V Pires, R C Melo-Minardi, , M A Santos, C H da Silveira, M M Santoro, and W Meira Junior. Cutoff Scanning Matrix (CSM): structural classification and function prediction by protein inter-residue distance patterns. BMC Genomics, 12 Suppl 4:S12, 2011.
Classificação estrutural e função por meio de contatos atômicos

Mapeamento através de distância cut off (0-30 A)
Redes de Funções Cerebrais
Baseadas em imagens de MRI

Mapeamento de determinadas regiões cerebrais em grafos

Análise da condição cerebral de indivíduos com doenças (Alzheimer, Esquizofrenia, Esclerose múltipla)
Interesse da comunidade médica (condições patogógicas estão envolvidas na conectividade entre cerebrais)

Interasse pelos neurocientistas para explorar a estrutura funcional do cérebro humano

Identificação de subgrafos (regiões densamente conectadas)
J.D. Power, et al. Functional network organization of the human brain. Neuron, 72(4):665–678, 2011.
Redes Sociais
Redes Biológicas
Redes de Informações
1. Conceito e modelagem de grafos
Definições básicas
Caminhamento em grafos
Isomorfismo de subgrafos
Mineração de padrões frequentes

2. Caracterização e análise de redes complexas
Tipos de redes
Medidas de centralidade
Coeficiente de agrupamento
Algoritmos para deteccão de comunidades
[1] M.E.J. Newman. The structure and function of complex networks. SIAM review, pages 167–256, 2003.

[2 ] Bondy, J.A.; Murty, U.S.R. (2008), Graph Theory, Springer.

[3 ] Biggs, N.; Lloyd, E. and Wilson, R. (1986), Graph Theory, 1736-1936, Oxford University Press.

[4] V M Goncalves-Almeida, D E V Pires, R C de Melo-Minardi, C H da Silveira, W Meira, and M M Santoro. Hydropace: understanding and predicting cross-inhibition in serine proteases through hydrophobic patch centroids. Bioinformatics, 28(3):342 9, February 2012.

[5] Zhan-Chao Li, Yan-Hua Lai, Li-Li Chen, Xuan Zhou, Zong Dai, and Xiao-Yong Zou. Identication of human protein complexes from local sub-graphs of protein-protein interaction network based on random forest with topological structure features. Anal Chim Acta, 718:32{41, March 2012.

[6] Miguel Lurgi and David Robertson. Automated experimentation in ecological networks. Autom Exp, 3(1):1, 2011.

[7] D E V Pires, R C Melo-Minardi, , M A Santos, C H da Silveira, M M Santoro, and W Meira Junior. Cuto Scanning Matrix (CSM): structural classification and function prediction by protein inter-residue distance patterns. BMC Genomics, 12 Suppl 4:S12, 2011.
P2P - Gnutella
Citações
Full transcript