Dissertação

TagSNP Selection Using Maximum Satisfiability EVALUATED

Na área da genética humana, tem sido dada especial atenção às variações genéticas entre seres humanos. A compreensão destas variações é essencial à melhoria no diagnóstico, na prevenção e no tratamento de doenças. Os Polimorfismos de Nucleótidos Simples (SNPs, do Inglês Single Nucleotide Polymorphisms) são as mais comuns variações entre seres humanos. Porém, dados os elevados custos envolvidos na análise do genótipo de um grande número de SNPs, é importante seleccionar um subconjunto mais pequeno de SNPs (tagSNPs) que melhor represente o conjunto de todos os SNPs, e capture o máximo de variação genética de uma população. Vários métodos foram já propostos para resolver o problema de determinar o número mínimo de tagSNPs. Neste trabalho analisamos soluções passadas que resolvem este problema. Apresentamos uma codificação para este problema numa variante do famoso problema de Satisfiabilidade (SAT), o problema de Máxima Satisfiabilidade (MaxSAT). Esta implementação aproveita o progresso feito recentemente no desenvolvimento de algoritmos SAT e MaxSAT muito eficientes. Tal facto resulta em bons desempenhos quando resolvemos instâncias do problema de selecção de tagSNPs, se compararmos esta implementação com outras desenvolvidas no passado. Neste trabalho desenvolvemos uma ferramenta que, tal como alguns algoritmos mais recentes, determina uma solução óptima para o problema de minimização considerado. Para além disso, é-nos possível com esta implementação, encontrar uma solução óptima considerando critérios secundários, de uma forma original face aos algoritmos existentes.
Polimorfismo de Nucleótido Simples, TagSNP, Problema de Satisfiabilidade, Problema de Máxima Satisfiabilidade

Janeiro 14, 2011, 11:0

Documentos da dissertação ainda não disponíveis publicamente

Orientação

CO-ORIENTADOR

Jaime Arsénio de Brito Ramos

Departamento de Matemática (DM)

Professor Auxiliar

ORIENTADOR

Maria Inês Camarate de Campos Lynce de Faria

Departamento de Engenharia Informática (DEI)

Professor Auxiliar