PROJECTOS DE INVESTIGAÇÃO
CIENTÍFICA E DESENVOLVIMENTO TECNOLÓGICO
BioGrid: Algoritmos Paralelos
para Anotação de Genes
RELATÓRIO FINAL
Relatório de Execução Material
REFERÊNCIA DO PROJECTO Nº
Data de
Entrada_____________________ Data
de Verificação__________________ Nº de Registo ______________________ Assinatura ________________________ Espaço reservado à Fundação
para a Ciência e a Tecnologia
Identificação da instituição proponente
Identificação da instituição proponente
Nome ou designação social INESC-ID: Instituto de Engenharia de
Sistemas e Computadores, Investigação e Desenvolvimento em Lisboa
Morada:
R. Alves Redol 9
Localidade:
Lisboa Código
postal: 1000
Telefone:
213100300 Fax:
213145843 Email:
aml@inesc-id.pt
Unidade responsável pela execução
do projecto
Nome:
Grupo de Algoritmos para Optimização e Simulação /
Knowledge Discovery and BioinformaticsMorada: R. Alves Redol 9
Localidade:
Lisboa Código
postal: 1000
Telefone
213100228 Fax
213145843 Email aml@inesc-id.pt
Identificação do investigador
responsável
Nome:
Arlindo Manuel Limede de Oliveira
Telefone
: 213100228 Fax :
213145843 Email:
aml@inesc-id.pt
Instituições
que participam no projecto
Não houve desvios relativamente ao projecto
original nas instituições que participam, que foram o INESC-ID e o Instituto
Gulbenkian da Ciência.
Equipa de investigação
|
|
CARGO/FUNÇÃO |
TAREFAS |
MESES |
|
Arlindo Manuel Limede de Oliveira |
Invest. Principal |
Coordenação |
17 |
|
Ana Teresa Correia de Freitas |
Investigadora |
T2, T4, T5 |
13 |
|
Sara Alexandra Cordeiro Madeira |
Investigadora |
T3, T5 |
21 |
|
José Carlos Pereira Monteiro |
Investigadora |
T1 |
4 |
|
Luís Miguel Pinto Silveira |
Investigador |
T1 |
4 |
|
Paulo Ferreira Flores |
Investigador |
T1 |
4 |
|
Paulo Ricardo Rodrigues Trezentos |
Investigador |
T1 |
10 |
|
Alexandre Paulo Lourenço Francisco |
Investigador |
T1 |
18 |
|
Miguel Mourão Fialho Bugalho |
Bolseiro Doutoramento FCT |
T1 |
21 |
|
Alexandra Sofia Martins Carvalho |
Bolseira Doutoramento FCT |
T2, T5 |
21 |
|
Ana Cristina Mercê Casimiro |
Bolseiro do projecto |
T2 |
13 |
|
José Miguel Ranhada Velez Caldas |
Bolseiro do projecto |
T2 |
20 |
|
Luís Pedro Fragão Bento Coelho |
Bolseiro do projecto |
T2, T4 |
20 |
|
Luís Manuel Silveira Russo |
Bolseiro Doutoramento FCT |
T4 |
9 |
|
Pedro Tiago Gonçalves Monteiro |
Bolseiro do projecto |
T2, T5 |
8 |
|
Ana Paula Proença Ramalho |
Bolseira do projecto |
T2, T3 |
8 |
|
Pooja Jain |
Bolseira do projecto |
T2, T5 |
5 |
|
Nuno Miguel Dias Mendes |
Bolseiro do projecto |
T2, T4, T5 |
12 |
|
Orlando Miguel Baptista Anunciação |
Bolseiro do projecto |
T2, T3 |
14 |
|
Sérgio Mendes Costa |
Bolseiro do projecto |
T1, T5 |
5 |
|
Pedro Menano Fernandes |
Investigador |
T1, T5 |
8 |
Esforço global
do projecto, expresso na unidade pessoa*mês
Unidade: em número
Instituição
Proponente (INESC-ID) 233
Instituição
2
Instituição 3
Instituição
4
Resumo dos trabalhos
desenvolvidos
Resumo
De acordo com o
planeamento original, o projecto tinha como objectivos contribuir para o avanço
do estado da arte no que respeita ao desenvolvimento de novas técnicas para a
análise de genomas. Inicialmente centrado em técnicas para detecção de genes,
os objectivos evoluiram, em consonância com os desenvolvimentos tecnológicos,
para a análise de outros motivos em genes, com ênfase especial na detecção de
motivos em regiões promotoras.
O trabalho encontra-se
dividido em 5 tarefas::
T1 - GRID para
bioinformática
T2 - Métodos para a
inferência de modelos sequenciais para previsão de motivos
T3 - Classificadores
para previsão de motivos
T4 - Implementação de
métodos baseados em homologia
T5 - Desenvolvimento de
um sistema para utilização pela comunidade de investigação em biologia
Com o avanço do projecto,
e o necessário ajuste do planeamento, os objectivos das tarefas foram ajustados
para os seguintes:
T1 - GRID para
bioinformática
T2 - Métodos e modelos
para análise de motivos em
T3 - Métodos supervisionados
e não supervisionados para análise de dados biológicos
T4 - Algoritmos
combinatórios para análise de sequências
T5 - Desenvolvimento de
um sistema para utilização pela comunidade de investigação em biologia
Esta reorientação das
tarefas corresponde a uma correcção dos objectivos que é natural num projecto
com esta duração, e que não afectou a finalidade última do mesmo, desenvolver,
implementar e disponibilizar algoritmos eficientes para a análise de dados genómicos
e de expressão, que usassem paradigmas de processamento paralelo em clusters e
grids.
A tarefas T2 evoluiu
para considerar também a aplicação destes métodos à descoberta de motivos nas
regiões promotoras, e das consequences relações com redes de regulação de
genes, para além do problema central originalmente definido de detecção de
regiões codificantes no genoma.
A tarefa T3 evoluiu no
sentido de aplicar não apenas métodos de aprendizagem supervisionada à análise
de dados biológicos, mas também métodos de aprendizagem não supervisionada à
análise de dados de expressão genética.
A tarefa T4 evoluiu no
sentido de considerar não apenas métodos baseados em homologias, mas também também outros algoritmos combinatórios eficientes
para análise de
As tarefas T1 e T5
mantiveram os seus objectivos inalterados, de acordo com a proposta original do
projecto.
Trabalhos realizados
No âmbito da tarefa T1,
foi, de acordo com o planeado, desenvolvida uma plataforma para a execução em
ambiente GRID de tarefas computacionalmente exigentes. Este esforço,
desenvolvido em colaboração com outros grupos do INESC-ID, resultou na
disponibilização de uma plataforma GRID, acessível a toda a comunidade de
investigadores da instituição [W.1]. Informação adicional sobre as
características da GRID, software e recursos disponíveis pode ser encontrada na
Newsletter institucional de Janeiro de 2006. Foi ainda desenvolvida
investigação no sentido de caracterizar GRIDs no que respeita à sua adequação a
tarefas, de acordo com macro-parâmetros que caracterizam o sistema [C.15]. Nesta
tarefa participaram, além do investigador principal, os investigadores Luís
Silveira, José Carlos Monteiro, Paulo Flores e Paulo Trezentos e a bolseira
Alexandra Carvalho.
A grid foi intensamente
utilizada não só como ferramenta de investigação, mas tambem como suporte à
execução de algoritmos computacionalmente intensivos, especialmente os que
estão a ser desenvolvidos no âmbito da tese de doutoramento do Miguel Bugalho [T.3][C.18],
das teses de mestrado do Alexandre Francisco [T.12] e Miguel Bugalho [T.14] e
da tese de graduação do Luís Coelho [T.17].
Os resultados obtidos em
termos de paralelização de métodos foram comunicados em diversas revistas [J.5]
e conferências [C.16].
No âmbito de tarefa T2,
foi desenvolvida significativa actividade de investigaçao em diversas áreas. De
acordo com o planeamento original, foram estudados métodos para a inferência de
modelos sequenciais [C.13][C.14] e a sua aplicabilidade a problemas de detecção
de motivos. Foram também estudados métodos para a detecção de regiões
codificantes [C.9], que foram disponibilizados na Web [A.1]. Nesta perspectiva,
foi desenvolvida uma tese de mestrado [T.8] que estudou o desenvolvimento de
novos kernels para a detecção de splice sites. O trabalho evoluiu depois para o
desenvolvimento de métodos para a detecção de motivos em regiões promotoras,
tendo sido desenvolvidos diversos algoritmos [J.2][J.3][C.11][C.12][R.2][R.3],
que foram disponibilizados para a comunidade científica [A.3].
Duas teses de
doutoramento [T.2][T.4], seis teses de mestrado [T.6][T.7][T.9][T.10][T.13][T.19]
e duas teses de graduação [T.15][T.17] foram desenvolvidas no contexto desta
tarefa.
No âmbito da tarefa T3, que
foi estendida para aplicar métodos baseados em aprendizagem automática não só à
análise de sequências, mas também à análise de expressão, encontra-se na sua
fase final uma tese de doutoramento [T.1]. Foram publicados diversos resultados
relativos à análise de dados de micro-arrays usando técnicas de aprendizagem
não supervisionada [J.6], com especial ênfase na análise de séries temporais
[C.2][C.5][C.7][C.10][R.1].
No âmbito da tarefa T4,
foi concluída uma tese de doutoramento [T.5] e publicados novos algoritmos para
indexação e processamento de sequências de símbolos [J.1][C.1][C.3][C.4][C.6][C.8][R.3],
que foram aplicados à procura de sequências em bases de dados em
Finalmente, no âmbito da
tarefa T5, foi definida a infra-eestrutura que veio a ser utilizada para
disponibilizar mais directamente à comunidade científica Portuguesa e
internacional as ferramentas desenvolvidas. Um sistema de informação biológica desenvolvido
no âmbito do grupo [J.4][A.5][C.17][T.11] permitiu criar competências na área, competências
estas que foram depois usadas na implementação e disponibilização das
ferramentas desenvolvidas, usando os recursos computacionais da grid do
A disponibilização dos
algoritmos desenvolvidos durante o projecto na web, usando as infra-estruturas
computacionais do Instituto Gulbenkian da Ciência foi efectuada durante os
últimos 6 meses do projecto [A.2][R.4][R.5]. O resultado desta
disponibilização, que foi o objectivo principal da tarefa T5, resultou num sistema
que não só é directamente utilizável, como já foi intensivamente utilizado por
investigadores e alunos.
Em particular, ficaram
disponíveis no sistema Hermes [W.2], instalado no Instituto Gulbenkian da
Ciência, os algoritmos PSMILE [C.16], MUSA [J.2], RISO [J.3],
Mais detalhes sobre a
execução de cada uma das tarefas encontram-se nos relatórios anuais, que foram
oportunamente enviados para a FCT, e que se anexam, em formato digital a este
relatório.
Conclusões
O projecto atingiu os
objectivos propostos, tendo tido como resultados mais significativos 6
publicações em revistas internacionais, 16 publicações em conferências
internacionais, 5 relatórios técnicos, numerosas aplicações computacionais
disponibilizadas para a comunidade científica, em 4 web sites diferentes, para
além de diversas teses de doutoramento, mestrado e graduação.
A disponibilização de cinco
algoritmos desenvolvidos no cluster do Instituto Gulbenkian da Ciência, onde
foram já extensivamente utilizados, representa provavelmente o resultado mais
visível, e que mais impacto poderá vir a ter no desenvolvimento desta área.
Em anexo a este
relatório encontram-se versões digitais dos documentos referidos no mesmo.
O investigador principal
agradece a colaboração de toda a equipa de investigação do projecto BioGrid,
que felicita pelos resultados alcançados.
Indicadores de realização física
Unidade: em número
A-
Publicações
Livros
Artigos em revistas internacionais 6
Artigos
em revistas nacionais
B-
Comunicações
Em congressos científicos
internacionais 16
Em
congressos científicos nacionais
C- Relatórios 5
D- Organização de seminários e conferências
E- Formação Avançada
Teses de Doutoramento 1 (terminada) 4 (em curso)
Teses de Mestrado 10
Outra (tese de graduação) 3
F- Modelos
G-
Aplicações computacionais 4
H- Instalações Piloto
I- Protótipos laboratoriais
J- Patentes
L-
Páginas Web 2
Publicações
Publicações com origem no projecto:.
Artigos em revistas
científicas:
[J.1] Luis Russo and Arlindo L. Oliveira, Efficient
generation of super condensed neighborhoods, Journal of Discrete Algorithms, 5(3), pp. 501-513, Sep. 2007,
Elsevier
[J.2] Nuno Mendes and Ana Casimiro and Pedro M. Santos
and Isabel Sá-Correia and Arlindo L. Oliveira and Ana T. Freitas, MUSA, a
parameter free algorithm for the identification of biologically significant
motifs, Bioinformatics, 22(24), pp.
2996-3002, Dec. 2006, Oxford Journals.
[J.3] Alexandra
M. Carvalho and Ana T. Freitas and Arlindo L. Oliveira and Marie-France Sagot,
An Efficient Algorithm for the Identification of Structured Motifs in
[J.4] Miguel C. Teixeira and Pedro Monteiro and Pooja
Jain and Sandra Tenreiro and Alexandra R. Fernandes and Nuno P. Mira and Marta
Alenquer and Ana T. Freitas and Arlindo L. Oliveira and Isabel Sá-Correia, The
YEASTRACT database: a tool for the analysis of transcription regulatory associations
in Saccharomyces cerevisiae, Nucleic
Acids Research, 34, pp. D446-D451, Jan. 2006, Oxford Journals
[J.5] Miguel Bugalho and Arlindo L. Oliveira,
Inference of regular languages using state merging algorithms with search, Pattern Recognition, 38(9), pp.
1457-1467, Sep. 2005, Elsevier.
[J.6] Sara C. Madeira and Arlindo L. Oliveira,
Biclustering algorithms for biological data analysis: a survey, IEEE/ACM
Transactions on Computational Biology and Bioinformatics, 1(1), pp. 24-45,
Jan. 2004, IEEE/ACM.
Artigos em conferências internacionais:
[C.1] Luís M. S. Russo, Gonzalo Navarro, Arlindo L.
Oliveira: Approximate String Matching with Lempel-Ziv Compressed Indexes. String
Processing and Information Retrieval, Oct. 2007, pp. 264-275, Springer.
[C.2] Sara C. Madeira and Arlindo L. Oliveira, An
Efficient Biclustering Algorithm for finding Genes with Similar Patterns in
Time-Series Expression Data, Asia Pacific Bioinformatics Conference, Jan. 2007
, pp. 67-80 , Imperial College Press
[C.3] Luis Russo and Arlindo L. Oliveira, A Compressed
Self-index Using a Ziv-Lempel Dictionary, String Processing and Information
Retrieval, Oct. 2006 , pp. 163-180 , Springer.
[C.4] Luis Coelho and Arlindo L. Oliveira, Dotted
Suffix Trees, A Structure for Approximate Text Indexing, String Processing and
Information Retrieval, Oct. 2006 , pp. 329-336 , Springer.
[C.5] Sara C. Madeira and Arlindo L. Oliveira,
Discovering Modules in Time-Series Gene Expression Data using Biclustering
(Abstract), IFCS Conference on Data Science and Classification, Jul. 2006
[C.6] Luis Russo and Arlindo L. Oliveira, Faster
Generation of Super Condensed Neighbourhoods Using Finite Automata, String
Processing and Information Retrieval, Nov. 2005, pp. 246-255 , Springer.
[C.7] Sara C. Madeira and Arlindo L. Oliveira, A
Linear Time Biclustering Algorithm for Time Series Gene Expression Data, 5th Workshop on Algorithms in Bioinformatics
(WABI), Oct. 2005 , pp. 39-52 , Springer.
[C.8] Luis Russo and Arlindo L. Oliveira, An Efficient
Algorithm for Generating Super Condensed Neighborhoods, Combinatorial Pattern
Matching: 16th Annual Symposium (CPM), Jun. 2005 , pp. 104-115 , Springer
[C.9] Pedro Monteiro and Ana Ramalho and Ana T.
Freitas and Arlindo L. Oliveira, DECIDE A Gene Finding Evaluation Tool, BKDB2005
- Bioinformatics: Knowledge Discovery in Biology, Jun. 2005 , pp. 68-72 .
[C.10] Sara C. Madeira and Arlindo L. Oliveira, A
linear time biclustering algorithm for time series gene expression data
(Abstract), The Learning Workshop, Mar. 2005.
[C.11] Alexandra M. Carvalho and Ana T. Freitas and
Arlindo L. Oliveira and Marie-France Sagot, A highly scalable algorithm for the extraction of
cis-regulatory regions, Proceedings of the 3rd Asia Pacific
Bioinformatics Conference, Jan. 2005 , pp. 273-282 , Imperial College Press
[C.12] Alexandra M. Carvalho and Ana T. Freitas and
Arlindo L. Oliveira and Marie-France Sagot, Efficient extraction of structured motifs using box
links,
Eleventh Symposium on String Processing and Information Retrieval, Out.
2004 , pp. 267-268 , Springer.
[C.13] Cláudia Martins Antunes and Arlindo L.
Oliveira, Sequential pattern mining algorithms: Trade-offs
between speed and memory, PKDD Workshop on Mining Graphs, Trees and
Sequences, Sep. 2004
[C.14] Cláudia Martins Antunes and Arlindo L. Oliveira,
Mining patterns using relaxations of user defined
constraints, PKDD Workshop on Knowledge Discovery in Inductive Databases,
Sep. 2004
[C.15] Paulo Trezentos and Arlindo L. Oliveira, Metrics for Grid Applicability: A Distributed
Elliptic Curve Platform Assessment, 5th Parallel Processing and Applied
Mathematics Conference, Apr. 2004 , pp. 864-871 , Springer.
[C.16] Alexandra M. Carvalho and Ana T. Freitas and
Arlindo L. Oliveira and Marie-France Sagot, A parallel algorithm for the extraction of structured
motifs,
19th ACM Symposium on Applied Computing, Mar. 2004 , pp. 147-153 , ACM.
[C.17] Pedro Monteiro and Miguel C. Teixeira and Pooja
Jain and Sandra Tenreiro and Alexandra R. Fernandes and Nuno Mira and Marta
Alenquer and Ana T. Freitas and Arlindo L. Oliveira and Isabel Sá Correia,
YEASTRACT: a database of transcription regulatory associations in Saccharomyces
cerevisiae, BKDB2005 - Bioinformatics:
Knowledge Discovery in Biology, Jun. 2005 , pp. 34-38.
[C.18] Miguel Bugalho and Arlindo L. Oliveira, Ab Initio
Protein Structure Prediction using Conformational Search and Information from
Known Protein Structures, Conference on the Critical Assessment of
Techniques for Protein Structure Prediction, Nov. 2006 .
Teses:
[T.1] Sara C. Madeira, Biclustering Algorithms for
Biological Data Analysis, PhD Thesis, Instituto Superior Técnico, Work in
progress
[T.2] Alexandra M. Carvalho, Efficient algorithms for
motif extraction in
[T.3] Miguel Bugalho, Search Based Methods for Proteín
Structure Prediction, PhD Thesis, Instituto Superior Técnico, Work in progress
[T.4] Nuno Mendes, Efficient algorithms for the
identification of miRNA motifs in
[T.5] Luis Russo, Enhanced Full-Text Self-Indexes
based on Lempel-Ziv Compression, PhD Thesis, Instituto Superior Técnico, Oct
2007
[T.6] José V. Caldas, Modelling and inference of gene
regulatory networks, MSc Thesis,
[T.7] Ana Casimiro, Análise de sequências de ADN:
contribuição do local de ocorrência para identificação de motivos biológicos
relevantes, MSc Thesis, Instituto Superior Técnico, May 2007
[T.8] Orlando Anunciação, Kernels para
Processamento de Cadeias de Caracteres em Problemas de Bioinformática, MSc
Thesis, Instituto Superior Técnico, Apr 2007
[T.9] Luis Coelho, Bayesian network parameter
estimation using noisy observations or soft evidence, MSc Thesis, Instituto
Superior Técnico, Jan 2007.
[T.10] Ana Ramalho, Métodos de biclustering para a
identificação de mecanismos de regulação genética, MSc Thesis, Instituto Superior
Técnico, Jul. 2006.
[T.11] Pedro Monteiro, Sistema de gestão da
informação genómica associada à regulação da transcrição em Saccharomyces
Cerevisiae, MSc Thesis, Instituto Superior Técnico, May 2005.
[T.12] Alexandre Francisco, Algoritmos para a
Predição de Estrutura Terciária de Proteínas, MSc Thesis, Instituto Superior
Técnico, Dec 2004.
[T.13] Alexandra M. Carvalho, Efficient Algorithms
for Structured Motif Extraction in
[T.14]
Miguel Bugalho, Inferência de Gramática Regulares usando Algoritmos de Fusão de
Estados com Procura, MSc Thesis, Instituto Superior Técnico, Mar 2004.
[T.15] José V. Caldas, Inferência de redes de
regulação genética usando técnicas de aprendizagem, Graduation Thesis, Instituto
Superior Técnico, Jul 2006.
[T.16] Christian Sá Nogueira and Carlos Oliveira,
Algoritmos para a Inferência de Redes de Regulação de Genes, Graduation Thesis,
Instituto Superior Técnico, Jul 2006.
[T.17] Ana Cristina Mercê Casimiro, Análise da
significância estatística de motivos em sequências de ADN, Graduation Thesis,
Instituto Superior Técnico, Sep 2005
[T.18] Luis Coelho, Paralelização de Algoritmos de
Exploração de Dados, Graduation Thesis, Instituto Superior Técnico, Aug 2004.
[T.19] Nuno Mendes, Inference of Complex Motifs Using
Biclustering Techniques, MSc Thesis, Instituto Superior Técnico, Nov 2005
Relatórios Técnicos:
[R.1] Sara C. Madeira and Arlindo L. Oliveira, An
Overview on Mixture and Hidden Markov Models of Gene Expression in Time-Series,
INESC-ID Tec. Rep. 41/2006, Dec 2006.
[R.2] José V. Caldas and Ana T. Freitas and Arlindo L.
Oliveira, Analysis of the dynamic behavior of gene regulatory networks,
INESC-ID Tec. Rep. 15/2006, Jul 2006.
[R.3] Luis Russo and Arlindo L. Oliveira, A Compressed
Self-Index using a Ziv-Lempel Dictionary, INESC-ID Tec. Rep. 6/2006, Mar 2006.
[R.4] BioGrid Motif Finding: Efficient Algorithms for
finding common motifs in
[R.5] BioGrid Biclustering: Biclustering algorithms
for gene expression data, Users Manual, Instituto Gulbenkian da Ciência
Aplicações computacionais:
[A.1] http://decide.inesc-id.pt
[A.2] http://hermes.igc.gulbenkian.pt/inquiry
[A.3] http://kdbio.inesc-id.pt/software
[A.4] http://www.yeastract.com
Páginas Web:
[W.1] http://grid.inesc-id.pt
[W.2]
http://hermes.igc.gulbenkian.pt