Projekte pro Jahr
Abstract
Recent technologies for typing single nucleotide polymorphisms (SNPs) across a population are producing genome-wide genotype data for tens of thousands of SNP sites. The emergence of such large data sets underscores the importance of algorithms for large-scale haplotyping. Common haplotyping approaches first partition the SNPs into blocks of high linkage-disequilibrium, and then infer haplotypes for each block separately. We investigate an integrated haplotyping approach where a partition of the SNPs into a minimum number of non-contiguous subsets is sought, such that each subset can be haplotyped under the perfect phylogeny model. We show that finding an optimum partition is
-hard even if we are guaranteed that two subsets suffice. On the positive side, we show that a variant of the problem, in which each subset is required to admit a perfect path phylogeny haplotyping, is solvable in polynomial time.
-hard even if we are guaranteed that two subsets suffice. On the positive side, we show that a variant of the problem, in which each subset is required to admit a perfect path phylogeny haplotyping, is solvable in polynomial time.
Originalsprache | Englisch |
---|---|
Zeitschrift | Discrete Mathematics |
Jahrgang | 2009 |
Ausgabenummer | 309(18) |
Seiten (von - bis) | 5610-5617 |
Publikationsstatus | Veröffentlicht - 2009 |
Projekte
- 1 Abgeschlossen
-
Komplexität von Haplotypisierungsproblemen
Tantau, T. (Projektleiter*in (PI)), Schnoor, I. (Beteiligte*r Wissenschaftler*in), Elberfeld, M. (Beteiligte*r Wissenschaftler*in), Kuczewski, J. (Beteiligte*r Wissenschaftler*in) & Pohlmann, J. (Beteiligte Person)
01.01.05 → 31.12.10
Projekt: DFG-Projekte › DFG Einzelförderungen