ÍslenskaenEnglish

Aðilar að Skemmunni

Leit eftir:


LokaverkefniHáskólinn í Reykjavík>Tölvunarfræðideild>Meistaraprófsritgerðir>

Vinsamlegast notið þetta auðkenni þegar þið vitnið til verksins eða tengið í það: http://hdl.handle.net/1946/7483

Titill
en

Models for solving mininum parsimony haplotyping

Efnisorð
Útgáfa
Júní 2007
Útdráttur
en

Single Nucleotide Polymorphisms (SNPs) are the most common form of variations in the human genome. Collection of SNP variants on a single chromosome copy are called haplotypes. Humans are diploid organisms, implying that they possess two nearly identical copies of each chromosome, and therefore the haplotypes come in pairs. Conflated (mixed) data from the two haplotypes is called a genotype of an individual. Minimum parsimony haplotyping (MPH) is an abstraction of haplotype finding problem arising in genetics, which tries to find the minimum set of haplotypes needed to explain a given set of genotypes. The MPH problem is known to be NP-Hard, meaning that finding computationally efficient solutions is unlikely in the general case. Here, we give novel efficient algorithms for sub-instances of the problem. In addition, a practical heuristic for MPH are implemented, solving problem instances for the general case. Experiments are done on real genotype data from the HapMap project [10] and heuristics developed from these experiments are used to speed up the implementation. These improvements result in a algorithm that solves MPH several times faster than previously described methods.

Athugasemdir

Tölvunarfræði, Project report

Birting
1.2.2011


Skrár
NafnRaðanlegtStærðRaðanlegtAðgangurRaðanlegtLýsingRaðanlegtSkráartegund
MSc_Steinunn-Maria... .pdf444KBOpinn Heildartexti PDF Skoða/Opna