Durante todo o período de pesquisa, houve participações em alguns eventos e a publicação de um artigo. Primeiramente, ocorreu a apresentação de um pôster no I Encontro Mineiro de Modelagem Computacional (EMMCOMP), em 2011, realizado na Universidade Federal de Juiz de Fora. Intitulado “Proposta de solução para o problema de montagem de fragmentos de DNA para sequenciadores de nova gera- ção”, o pôster se baseava em uma das primeiras propostas discutidas, que envolvia a aplicação de uma metaheurística no lugar do método de Munkres para cálculo do emparelhamento máximo de peso máximo.
Foi apresentado um poster também no X-Meeting 2011, evento organizado pela Associação Brasileira de Bioinformática e Biologia Computacional (AB3C) em Florianópolis. Intitulado “Resolving Problematic Topologies in k-mer graphs: a pro- posal of a new method for DNA fragment assembly”, o trabalho também abordava a estratégia de uso de uma metaheurística para solucionar as topologias (empare- lhamento máximo de peso máximo).
Por último, foi apresentado um artigo na XXXI International Conference of the Chilean Computer Science Society (SCCC 2012), intitulado “Theoretical basis of a new method for DNA fragment assembly in k-mer graphs” [Couto et al., 2012]. Este artigo, por sua vez (disponível no Apêndice B), já aborda uma proposta parecida com a deste trabalho, diferenciando-se na construção de caminhos após a obtenção dos unipaths.
Discussão
5.1
Resultados versus Objetivos
O objetivo geral deste trabalho era o desenvolvimento de uma nova abordagem de montagem, que evitasse ao máximo as etapas de pré e pós-processamento (seção 1.2, página 3). Após executar os testes com as quatro espécies, pôde-se perceber que a ferramenta consegue efetuar a montagem completa em metade dos casos com cobertura igual a 80 e k = 31. Para k a partir de 41, Candidatus Sulcia muelleri apresenta uma montagem adequada, já que os múltiplos matches não interfere na qualidade do maior match, que obteve tamanho próximo do original. Apesar de não ter atingido resultados completos nas última espécie, este resultado já permite construir uma validação inicial da ferramenta.
Nos resultados em que se obteve consensos de menor qualidade, percebe-se que a ambiguidade é um dos complicadores. A presença de dados de ambas as fitas do DNA, por exemplo, podem criar casos em que se obtém consensos são maiores do que o genoma original. Trechos de fitas diferentes que possuam trechos similares podem se conectar durante a construção do grafo, criando arcos (excluídos durante o cálculo do emparelhamento) que gerarão combinações de caminho que não representam a realidade. A Figura 5.1 apresenta um exemplo deste caso.
Na Figura 5.1, vê-se que alguns fragmentos de ambas as fitas produzem k-mers em comum. Isso provoca a conexão errônea entre as duas fitas de DNA, prejudicando o resultado final. Apesar de não acontecer em todos os casos, é interessante analisar possibilidades de filtragem de dados de entrada, se possível de forma unificada com a montagem do grafo, evitando a presença de dados de ambas as fitas. No exemplo da figura, os consensos possuem sequência de tamanho 10, maior do que o genoma original (8 nucleotídeos).
Figura 5.1. Conexões entre sequências de fitas diferentes. Em (A), vê-se um genoma fictício, com o sentido de cada fita destacado por setas pontilhadas. Os fragmentos de tamanho 3 gerados a partir dos fragmentos estão à direita. Em (B), o grafo k-mer, com k = 2, é apresentado. Os consensos obtidos são representados por setas pontilhadas. Em (C), os consensos em forma textual.
O montador Velvet [Zerbino & Birney, 2008] (seção 2.4.4.2), por exemplo, utiliza uma forma adaptada do grafo k-mer, em que todo k-mer carregado no grafo tem imediatamente seu complemento calculado e conectado, formando um “nó”. Isso unifica os dados, evitando que a fita direta e a reversa sejam representadas de forma separada. Assim, não há a possibilidade da sequência de uma fita se conectar com a sequência da outra. O SHARCGS [Dohm et al., 2007] (seção 2.4.1.3), por sua vez, também possui um controle dos reads, buscando evitar que a sequência de um read esteja presente mais de uma vez no grafo e, para cada read, gera seu complemento reverso automaticamente.
O valor de k, ou seja, o comprimento da sequência de cada vértice, também influencia no resultado da montagem. Para Candidatus Sulcia muelleri, um valor de k igual a 41 já foi suficiente para parar de retornar um consenso com o tamanho maior do que o genoma original, eliminando ligações errôneas. No caso dos testes com Candidatus Tremblaya princeps, o valor de k = 51 reduziu bastante o tamanho do consenso, que era muito maior do que o genoma. Porém, esse ainda manteve ligações errôneas. Para k = 61, o resultado piorou. É compreensível que este genoma apresente mais problemas do que os outros três testados, já que possui áreas de repeat com cerca de 5 mil pares de base, o que dificulta bastante a montagem.
É interessante que se implemente o controle das sequências de cada fita em próximas versões desta ferramenta. Este controle e a calibragem de valores de k para cada genoma podem trazer melhorias importantes nos resultados.
A complexidade e a quantidade de memória, se comparados com o tamanho total dos genomas, são altas. Entretanto, por se tratar de um trabalho inicial, é aceitável que este apresente problemas e alguns ajustes necessários. A diminuição da complexidade e a utilização de threads em mais partes do algoritmo podem contribuir para a melhoria da eficiência do algoritmo.
Apesar de apresentar problemas em alguns reasultados, há que se concordar que a ferramenta mostrou ser possível efetuar a montagem em menos passos, já que alguns genomas foram montados. A diminuição da memória gasta possibilitará o teste do montador em outros cenários.
O fato do processo de cruzamento de caminhos ser uma heurística torna difícil prever com exatidão o tempo total gasto de acordo com o tamanho dos dados, como pode ser observado na Tabela 4.1 (página 55). Nesse contexto, o tempo de processamento do algoritmo não é completamente influenciado pelo tamanho dos dados de entrada. O tamanho da entrada influencia principalmente os passos executados de forma exata, até a geração de unipaths. O uso de delimitadores de tempo máximo ou número máximo de ciclos de cruzamento de caminhos representa uma boa alternativa caso os tempos de execução se mostrem maiores em outros casos experimentais.
Embora a solução tenha sido inicialmente validada, é necessário que se promova testes com outras espécies (mais complexas e de genoma maior) e também compa- rativos com montadores de contexto similar para que se tenha uma ferramenta mais robusta e competitiva. Testes de montagem híbrida (em que se emprega mais de uma ferramenta durante a montagem) também podem ser positivos, mas fogem da proposta deste protótipo.
Outra alternativa para diminuir os custos computacionais da ferramenta pode ser o uso de uma linguagem que não necessite de máquina virtual, ou seja, que trabalhe de maneira independente. Estas linguagens tendem a ser de mais leve processamento e algumas delas são muito fortes na área de Bioinformática, como Perl1 (com seus pacotes para a área, no projeto BioPerl2), Python3 e outras. Estas linguagens não foram utilizadas neste trabalho por causa da curva de aprendizado necessária para utilizá-las. Além disso, a linguagem Java foi inicialmente selecio- nada por conta de algumas bibliotecas já desenvolvidas por terceiros que poderiam ser incorporadas. Após alterações no protótipo, porém, apenas o código de empa- relhamento máximo de peso máximo foi incorporado.
1 http://www.perl.org/ 2 http://www.bioperl.org/wiki/Main_Page 3 http://www.python.org/
O desenvolvimento deste protótipo demonstra a real aplicabilidade da téc- nica e indica a necessidade de aprimoramentos para que esse possa se tornar uma ferramenta para uso da comunidade de genômica em geral.
Conclusões e Perspectivas
6.1
Conclusões
A solução desenvolvida conseguiu efetuar a montagem de alguns genomas de forma satisfatória. Para outros, alguns problemas não puderam ser totalmente resolvidos. Apesar disso, pode-se concluir que a solução foi validada. O algoritmo evitou as cor- reções de erros em k-mers e correções para cada topologia problemática, pois foram realizadas implicitamente na execução do algoritmo, além dos pós-processamentos, diminuindo o número de passos para a montagem.
Apesar de ter mostrado que a proposta é promissora, porém, percebe-se que há algumas melhorias a serem realizadas. Adaptações na estruturas de dados em- pregadas atualmente, bem como o corte na complexidade de algumas operações realizadas e na memória gasta podem proporcionar o refinamento que a ferramenta precisa, se transformando em uma ferramenta mais madura.
Percebe-se que a cobertura influi diretamente na qualidade das montagens, tendo em vista a mudança na qualidade da montagem do genoma de uma das espécies com a mudança da cobertura de 30 para 80. Os erros de sequenciamento, como se tornou possível perceber, podem ser contornados pelo emparelhamento máximo de peso máximo e a aplicação do emparelhamento apenas nas componentes conexas oferece diminuição na complexidade real do código.
Por fim, conclui-se que este trabalho atingiu os objetivos gerais e específicos, pois a abordagem foi desenvolvida, aplicada em espécies selecionadas e teve seus resultados analisados. Como uma ferramenta validada inicialmente, porém, há al- gumas melhorias e alterações possíveis em trabalhos futuros.