Nyligen genomförda studier har visat att de mönster av kopplingsdisequilibrium som observerats i humana populationer har en blockliknande struktur, och en liten delmängd av SNPs (kallas tagg SNPs) är tillräcklig för att särskilja varje par av haplotyp mönster i blocket. I själva verket kan vissa tagg SNP saknas, och vi kan misslyckas med att skilja två olika haplotyper på grund av den tvetydighet som orsakas av saknade data. Vi visar att det finns en undergrupp av SNPs (kallas robusta tagg SNPs) som fortfarande kan särskilja alla distinkta haplotyper även när vissa SNPs saknas. Problemet med att hitta minsta robusta tagg SNP visas vara NP-hård. För att hitta robusta tagg SNPs effektivt föreslår vi två giriga algoritmer och en linjär programmeringsavslappningsalgoritm. De experimentella resultaten indikerar att (1) de lösningar som hittas av dessa algoritmer är ganska nära den optimala lösningen; (2) genotypningskostnaden som sparas genom att använda tagg SNPs kan vara så hög som 80%; och (3) genotypa ytterligare tagg SNPs för att tolerera saknade data är fortfarande kostnadseffektivt. Genotypning robust tagg SNPs är mer praktiskt än bara genotypa den minsta taggen SNPs om vi inte kan undvika förekomsten av saknade data. Vår teoretiska analys och experimentella resultat visar att prestandan hos våra algoritmer inte bara är effektiv utan att den lösning som hittas också är nära den optimala lösningen.
Detta problem formulerades av REF som en uppsättning k-täckning problem och visade sig vara NP-hård.
Selecting additional tag SNPs for tolerating missing data in genotyping
{'venue': 'BMC Bioinformatics', 'journal': 'BMC Bioinformatics', 'mag_field_of_study': ['Medicine', 'Biology', 'Computer Science']}