Identificação de genes e o problema do alinhamento Spliced Múltiplo

Abstract

A identificação de genes em sequências de DNA de organismos eucariotos ainda pode ser considerado um problema em aberto na Bioinformática. Na busca por soluções deste problema, em muitos casos recorre-se à comparação de sequências. Várias combinações de sequências vêm sendo utilizadas pelas ferramentas de identificação de genes e neste trabalho propomos a comparação de diversas sequências de cDNA com uma sequência de DNA. Essa proposta foi abordada através da formulação e estudo de um problema de otimização combinatória denominado Problema do Alinhamento Spliced Múltiplo. Nessa dissertação descrevemos esse problema, demonstramos que ele é NP-completo para a distância de Levenshtein e propomos quatro heurísticas para resolvê-lo. Com base nessas heur´ısticas, desenvolvemos quatro ferramentas de identificação de genes por comparação de uma sequência de DNA com várias sequências de cDNA. Essas ferramentas foram avaliadas em instâncias de teste que construímos a partir de dados reais do genoma humano e os seus resultados mostraram-se melhores que os de outras ferramentas de identificação de genes disponíveis na literatura.

The gene prediction in DNA sequences of eukariotic organisms is still an open problem in Bioinformatics. The sequence comparison based approach is commonly used in the search of solutions for this problem. Several different combinations of sequences are being used by gene recognition tools and in this work we propose the comparison of many cDNA sequences with a DNA sequence. This proposal was addressed by the formulation and study of a combinatorial optimization problem, called Multiple Spliced Alignment Problem. In this work we describe this problem, show that it is NP-complete under the Levenshtein distance and propose four heuristics to solve it. Based on these heuristics, we developed four gene recognition tools based on the comparison of a DNA sequence with many cDNAs. These tools were evaluated with instances built from real human genome data and their results were better when compared to other gene recognition tools available in literature.