FenixEdu™

Dissertação

Error Detection in Pedigrees Using Satisfiability-Based Aproaches EVALUATED

Detalhes: No campo da biologia computacional, um pedigree é uma estrutura que permite a monitorização de indivíduos e correspondentes relações familiares. Com pedigrees, torna-se possível seguir o fluxo de informação genética desde os progenitores até aos seus descendentes. Contudo, com o elevado desempenho das técnicas actuais de genotipagem, a ocorrência de erros em pedigrees torna-se cada vez mais um problema da maior importância e a consistência vai sendo cada vez mais algo com que os geneticistas têm de lidar. O problema da verificação da consistência de pedigrees consiste na problemática de verificar se um pedigree (uma árvore geneológica com informação de genes associada) é ou não consistente com as leis de hereditariedade de Mendel. Esta verfificação de consistência é um problema NP-completo bastante conhecido e existem dois tipos principais de abordagens que o tentam resolver: abordagens estatísticas e abordagens combinatoriais. O objectivo deste trabalho consiste na tentativa de desenvolvimento de dois tipos de abordagens combinatoriais baseadas em satisfação (suporte mínimo e codificação k-AC) e tentar medir a sua eficácia com distintos tipos de instâncias.
Keywords: Pedigrees, NP-completo, Satisfação, Suporte Mínimo, Codificação k-AC

Discussão: novembro 6, 2009, 15:15