Proposal of a new approach for the de novo assembly process of DNA sequences from new generation sequencers

O estudo de genomas trouxe muitos ganhos para a medicina, farmacologia e di- versas outras áreas do conhecimento. Porém, muitos desafios também surgiram como consequência, em especial os computacionais. A grande massa de dados e sua complexidade para ser analisada tornam difícil o ato de extrair as informações neces- sárias. Como os sequenciadores de DNA não conseguem trabalhar com a molécula completa de uma vez, o sequenciador quebra a molécula e trabalha com diversos fragmentos, que precisam ser montados em um próximo passo. Nos sequenciadores de nova geração, o processo de sequenciamento é muito mais rápido e mais barato, mas também traz fragmentos muito menores do que aqueles obtidos na tecnologia Sanger. Além do maior número de fragmentos, a interferência dos erros de sequen- ciamento torna o processo complicado, sendo classificado como NP-Difícil. Para resolver esta situação, os montadores de fragmentos de DNA atuais executam uma série de pré e pós-processamentos nos dados gerados, a fim de eliminar ou pelo menos diminuir os desafios presentes. Neste trabalho, propõe-se uma nova abor- dagem de emparelhamento máximo de peso máximo (anteriormente proposta para fragmentos da tecnologia Sanger) em grafos k-mer, que retorna componentes mais simples de trabalhar (conhecidos como unipaths), junto com uma heurística para combinar esses componentes. Assim, busca-se fazer o processo de montagem em menos etapas. Este cruzamento trabalha com a extensão de caminhos através da combinação dos unipaths. Com um sistema de pontuação, o montador busca cons- truir caminhos maiores e com o mínimo de áreas repetidas. Por se tratar do início de uma nova abordagem para fragmentos curtos, este trabalho não visa obter um xmontador de DNA completo em sua primeira versão, mas validar o conceito pro- posto. Neste trabalho, foca-se especificamente na montagem de sequências obtidas de sequenciadores da nova geração. Durante os testes, percebeu-se que o protótipo consegue montar satisfatoriamente os genomas em metade dos casos, necessitando de alguns ajustes em próximas versões para os demais casos. Estes ajustes solucio- nariam problemas específicos que esta ferramenta ainda não soluciona. Levantou-se também que a cobertura de reads é fator determinante para bons resultados desta ferramenta. Há alguns trabalhos futuros necessários, como corte do gasto de memó- ria, diminuição do tempo de processamento e comparação com outras ferramentas disponíveis atualmente.The study of genomes brought a lot of gains to Medicine, Pharmacology and many other important science fields. However, many challenges emerged as a consequence, specially in Computer Science. The big amount of data and its complexity to be analyzed make arduous to extract the information needed. As the DNA sequencers are not able to get the sequence of the whole molecule at a glance, the sequencing process breaks the molecule and works with a lot of fragments. Those fragments need to be assembled in a next step. In the new-generation sequencers, the sequen- cing process is much faster and cheaper, but they return much smaller fragments compared to the output from Sanger technology. Besides the bigger set of fragments, the interference of sequencing errors complicates the process, classified as NP-hard. To handle this problem, the current DNA fragment assemblers run a lot of pre and postprocesses in the amount of data, aiming to eliminate or at least reduce the common problems. In this work, we propose a new approach of maximum- weighted maximum matching (first proposed for data from Sanger sequencing) for k-mer graphs that returns simpler components to work with (called unipaths), fol- lowed by an heuristic to combine those new components. Therefore, we want to do the assembly process in fewer steps. This crossing works with elongation of paths by the combination of unipaths. With a score system, the assembler tries to get longer paths combining the shorter ones, while minimizing the use of repeated re- gions. Because this is the beginning of a new approach for short fragments, it was not our intention to achieve a complete DNA assembler at its first version, but only to validate the proposed concept. In this work, we give focus specifically on the xiiassembly of sequences from new-generation sequencers. During the experiments, we identified that the assembler was able to return satisfatory results for half of the samples, but it needs some adjustments to improve the other results. Those adjust- ments would solve specific problems that this tool does not address yet. We also found out that the coverage by reads is determinant factor to get good outputs from this assembler. There are some future works that are necessary, such as decreasing memory usage and running time, as well as comparing this tool with other current available solutions.Coordenação de Aperfeiçoamento de Pessoal de Nível Superio