Use este identificador para citar ou linkar para este item: https://locus.ufv.br//handle/123456789/2677
Tipo: Dissertação
Título: Proposta de uma nova abordagem para o processo de montagem de novo de sequências de DNA obtidas de sequenciadores de nova geração
Título(s) alternativo(s): Proposal of a new approach for the de novo assembly process of DNA sequences from new generation sequencers
Autor(es): Couto, Adriano Donato
Primeiro Orientador: Cerqueira, Fábio Ribeiro
Primeiro coorientador: Oliveira, Alcione de Paiva
Primeiro avaliador: Fietto, Juliana Lopes Rangel
Segundo avaliador: Ferreira, Ricardo dos Santos
Abstract: 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.
Palavras-chave: Bioinformática
Genômica
Sequenciamento de nucleotídeo
Teoria dos grafos
Bioinformatics
Genomics
Nucleotide sequencing
Graph theory
CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Idioma: por
País: BR
Editor: Universidade Federal de Viçosa
Sigla da Instituição: UFV
Departamento: Metodologias e técnicas da Computação; Sistemas de Computação
Programa: Mestrado em Ciência da Computação
Citação: COUTO, Adriano Donato. Proposal of a new approach for the de novo assembly process of DNA sequences from new generation sequencers. 2014. 99 f. Dissertação (Mestrado em Metodologias e técnicas da Computação; Sistemas de Computação) - Universidade Federal de Viçosa, Viçosa, 2014.
Tipo de Acesso: Acesso Aberto
URI: http://locus.ufv.br/handle/123456789/2677
Data do documento: 27-Fev-2014
Aparece nas coleções:Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
texto completo.pdf4,28 MBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.