ABSTRACT Haplotype inference är ett viktigt steg för många typer av analyser av genetisk variation i det mänskliga genomet. Traditionella metoder för att erhålla haplotyper innebär att samla in genotypinformation från en population av individer och sedan tillämpa en haplotype inference algoritm. Utvecklingen av teknik för sekvensering med hög genomströmning möjliggör en alternativ strategi för att erhålla haplotyper genom att kombinera sekvensfragment. Problemet med "haplotype sammansättning" är problemet med att montera de två haplotyperna för en kromosom med tanke på insamlingen av sådana fragment, eller avläsningar, och deras placering i haplotyperna, som är förutbestämda genom att kartlägga avläsningarna till ett referensgenom. Fel i avläsningar ökar avsevärt svårigheten med problemet och det har visat sig att problemet är NP-hård även för avläsningar av längd 2. Befintliga giriga och stokastiska algoritmer är inte garanterade att hitta optimala lösningar för haplotype monteringsproblem. Resultat: I den här artikeln föreslog vi en dynamisk programmeringsalgoritm som kan montera haplotyperna optimalt med tidskomplexitet O(m×2 k ×n), där m är antalet avläsningar, k är längden på den längsta avläsningen och n är det totala antalet SNPs i haplotyperna. Vi minskar också problemet med montering av haplotyp till det maximala tillfredsställande problemet som ofta kan lösas optimalt även när k är stort. Genom att dra nytta av effektiviteten i vår algoritm utför vi simuleringsexperiment som visar att montering av haplotyper med avläsningar av längd som är typiska för den nuvarande sekvenseringsteknologin inte är praktiskt. Vi visar dock att kombinationen av detta tillvägagångssätt och de traditionella infasningsmetoderna för haplotyp gör det möjligt för oss att praktiskt bygga haplotyper som innehåller både vanliga och sällsynta varianter. Kontaktuppgifter:
Det finns också en exakt dynamisk programmering lösning till SIH problemet; dess körtid är exponentiellt i längden på den längsta lästa REF.
Optimal algorithms for haplotype assembly from whole-genome sequence data
{'venue': 'Bioinformatics', 'journal': 'Bioinformatics', 'mag_field_of_study': ['Computer Science', 'Medicine']}