Montagem de fragmentos de DNA pelo metodo ' Ordered Shotgun Sequencing' (OSS)

Orientador: João Meidanis Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Esta dissertação é na área de Biologia Computacional e se propõe a estudar a montagem de fragmentos de DNA pelo método Ordered Shotgun Sequencing (088). A montagem de fragmentos de DNA é uma das etapas de um projeto de seqüenciamento total do genoma de um organismo. Com o crescimento do tamanho dos genomas a serem seqüenciados e do aumento da complexidade dos organismos estudados, os problemas para se montar um DNA, como trechos repetidos no genoma, também aumentaram. Até os anos noventa, o método mais popular de montagem de fragmentos era o 8hotgun, que quebra a molécula de DNA em fragmentos de mais ou menos 500 pares de bases que serão desvendados em laboratórios de seqüenciamento. Conhecendo-se os fragmentos, é a vez de se descobrir como eles se encaixam, através de sobreposições, e ordená-los. No final, espera-se que os algoritmos nos retomem a seqüência do DNA. Em 1993, dois biólogos propuseram a montagem de fragmentos 088, que quebra a molécula de DNA em intervalos bem maiores, resultando em fragmentos que chamaremos de clones, e seqüencia apenas as suas pontas, deixando a parte central desconhecida. Agora, além da seqüência dos fragmentos, teremos a informação de ligação e distância entre as pontas do clone. Com essas informações e das sobreposições entre as pontas" tenta-se encontrar as posições relativas dos clones no DNA. Um bloco ordenado de fragmentos de DNA por causa das sobreposições e das ligações de clone, será denominado scaffold. As suas partes desconhecidas serão desvendadas em outras iterações, que é uma característica da montagem de fragmentos de DNA 08S. Em 1998, ano que nossos estudos começaram, não haviam trabalhos computacionais que tirassem proveito dessa técnica, até que em 2000 surgiram trabalhos relatando projetos genoma que utilizaram a montagem OS8 com sucesso. Em nosso trabalho, propusemos dois algoritmos para encontrar scaffolds e um ambiente de simulação para executar as iterações feitas pelo método 088 e montar genomas artificialmente gerados. Foram feitos vários testes para medir o desempenho dos algoritmos propostos em termos de tempo total de processamento em CPU, e número de iterações e de clones seqüenciados para terminar a montagem 088. Por último, identificamos várias questões importantes sobre os algoritmos que merecem um estudo mais aprofundado. Abstract: This is a dissertation in the area of Computational Biology. We propose to study the DNA fragment assembly problem using the Ordered Shotgun Sequencing (OSS) method. The DNA fragment assembly problem is one step of a complete genome sequencing project. With the growing size of the sequenced genomes and the increasing complexity of the studied organisms, problems such as repeated regions increased as well. The OSS method is an attempt to mitigate those problems. Until the nineties, the most popular method of DNA fragment assembly was Shotgun, which breaks the DN A inolecule into pieces of about 500 base pairs that are revealed by sequencing laboratories. Given the fragments, it is necessary to find out what their relative position is in the original DNA molecule by using overlap information to order them. In the end, the algorithms are supposed to give us the DNA sequence. In 1993 two biologists proposed the OSS method for fragment assembly, which breaks the DNA into quite bigger pieces, resulting in fragments called clones in this dissertation. Just the ends of the clones are sequenced, leaving the central part unknown. Besides the fragment sequences, we know how far one end is from the other, and their relative orientation. Based on this information and on the overlaps between done ends, a~ ordered block of DNA fragments called scaffold can be formed. The unknown part will be revealed by subsequent iterations, an intrinsic characteristic of OSS DNA fragment assembly. Our studies began in 1998 when there was no computational work exploring the OSS technique. The first papers reporting on the successful use of OSS assembly in genome projects appeared in 2000 In this work, we propose two scaffold-finding algorithms and present a simulation environment built to test them. The environment generates artificial data, promotes the iterations, and keeps track of the amount of sequencing, number of iterations, and processing time for the algorithm being tested. Finally, we identified many important questions about the algorithms which deserve further studies. Mestrado Mestre em Ciência da Computação