Um método híbrido para inferência de haplótipos por parcimônia

Um grande desafio em Biologia hoje é associar mutações no DNA a várias características dos organismos, especialmente as relacionados com doenças. Muitas investigações sobre mutações que ocorrem no genoma foram realizadas, levando à conclusão de que alterações pontuais que ocorrem em regiões conservadas do DNA, que podem ser transmitidas através de várias gerações, podem ser associadas com a ocorrência de certas características ou doenças. Como consequência, mapear estas alterações e relacioná-las à ocorrência ou propensão de condições específicas é muito desejável. Infelizmente, esta tarefa não é fácil, pois para localizar estas mutações é necessário ter acesso ao haplótipo de um indivíduo, o que é um procedimento muito custoso, considerando a tecnologia corrente. Desta forma, métodos computacionais para inferência de haplótipos a partir de dados genotípicos são altamente necessários. Muitas abordagens foram propostas, mas nenhuma representa uma proposta completamente satisfatória, uma vez que os custos computacionais associados aos procedimentos são proibitivos ou as soluções encontradas são de baixa qualidade. A demanda principal corrente na pesquisa em inferência de haplótipos é que os métodos possam lidar com grandes volumes de dados genotípicos. Devido ao crescimento exponencial do custo das abordagens computacionais exatas, métodos que oferecem soluções rápidas com qualidade aceitável são altamente desejáveis. Nesta dissertação um novo método, chamado HybridPTG, é proposto. É uma abordagem híbrida que usa Cadeias de Markov para reduzir drasticamente a necessidade de passos randômicos (na média necessita de 99,99% menos operações aleatórias que o original PTG), convergindo para boas soluções (soluções similares ou melhores que as do método PTG) em poucos, frequentemente menos de dois, passos, portanto com uma complexidade computacional consideravelmente menor do que abordagens randômicas (tempo de processamento). Diversos experimentos com conjuntos de dados genotípicos de diferentes características foram realizados para comparar HybridPTG aos melhores algoritmos conhecidos, PTG, FastPHASE e Haplorec, mostrando que HybridPTG é um método bastante estável, confiável e eficienteCoordenação de Aperfeiçoamento de Pessoal de Nível Superio