Um algoritmo para comparação sintatica de genomas baseado na complexidade condicional de Kolmogorov

Desde 1953, quando Natson e Crick desvendaram a estrutura do DNA (ácido desoxirribonucleico), a área de Biologia Molecular tem avançado rapidamente. Técnicas que permitem a manipulação de biomoléculas foram criadas e aperfeiçoadas desde então, gerando enormes quantidades de dados. A necessidade de processar estas informações criou um novo campo chamado de Biologia Molecular Computacional, o qual consiste em desenvolver e usar técnicas matemáticas e de computação para ajudar a resolver problemas de Biologia Molecular. Existem problemas desta área relacionados a Comparação de Genomas, que consiste, a grosso modo, em analisar e comparar seqüências de ácidos nucléicos ou aminoácidos entre espécies. A comparação de genomas busca desvendar as relações existentes entre diferentes espécies. A descoberta de genes ou porções semelhantes nos genomas pode indicar proximidade evolutiva ou regiões indispensáveis à existência da vida. Por outro lado, as diferenças podem relacionar o comportamento particular de uma espécie com uma determinada região de seu genoma. Diante destas observações, iniciamos o desenvolvimento de um algoritmo que realiza a comparação sintática de genomas baseado nos trabalhos de Li e colegas, que utilizam a Complexidade de Kolmogorov para medir a distância entre dois genomas. Ao invés de uma medida de distância, o algoritmo proposto indica as regiões similares entre genomas que são consideradas relevantes pelo critério da Complexidade Condicional de KolmogorovSince 1953, when Watson and Crick discovered the DNA (deoxiribonucleic acid) structure, Molecular Biology has advanced quickly. Techniques were developed and improved to manipulate biomolecules since that, generating huge quantities of data. The need to process this information created a new field called Computational Molecular Biology, which consists in the development and usage of mathematical and computing techniques to solve Molecular Biology problems. There are problems in that are a related to Genome Comparison, which consists, roughly speaking, in analysis and comparison of nucleic acid or aminoacid sequences between species. Genome Comparison tries to reveal existing relationships between species. The discovery of similar genes or pieces in genomes can point out evolutionary proximity or indispensable regions for life existence. Besides, differences can relate the unique behavior of a species with some of its genome regions. Based on these observations, we start the development of an algorithm that makes sintatic genome comparison using some ideas of Li and colleagues. They work with Kolmogorov Complexity to measure the distance between two genomes. Instead of a distance measure, the proposed algorithm shows similar regions that are considered relevant by the Conditional Kolmogorov Complexity criteri