### Skapa referens, olika format (klipp och klistra)

**Harvard**

Damaschke, P. (2004) *Incremental haplotype inference, phylogeny, and almost bipartite graphs*.

** BibTeX **

@conference{

Damaschke2004,

author={Damaschke, Peter},

title={Incremental haplotype inference, phylogeny, and almost bipartite graphs},

booktitle={2nd RECOMB Satellite Workshop on Computational Methods for SNPs and Haplotypes, Proceedings (Prepint), Carnegie Mellon University, Pittsburgh 2004 },

pages={1-11},

abstract={The paper addresses the combinatorial problem of inferring the unknown haplotypes in a population, given a sample of genotypes, under the assumption that the population forms
a perfect phylogeny (PP). It is important because physical haplotyping by DNA sequencing is expensive, whereas
genotypes are easier to obtain. Since PPs appear naturally and quite frequently, PP haplotyping is a favourable approach to reliable haplotype inference. Since Gusfield's paper from 2002, a few different algorithms have been proposed. Here we show that an extremely simple algorithm identifies, under the random mating assumption, all sufficiently frequent haplotypes in a random sample of
genotypes of asymptotically optimal size. Missing data can also be recovered if they are not too prevalent. Moreover, the idea of the algorithm easily extends to more general population structures than PP. We also solve a problem we call almost 2-coloring of graphs, which arises in an enhanced version of our haplotyping algorithm. We show that the solution space of this graph problem can be computed in linear time. },

year={2004},

keywords={haplotype phasing, perfect phylogeny, random mating, bipartite
graphs},

}

** RefWorks **

RT Conference Proceedings

SR Print

ID 1669

A1 Damaschke, Peter

T1 Incremental haplotype inference, phylogeny, and almost bipartite graphs

YR 2004

T2 2nd RECOMB Satellite Workshop on Computational Methods for SNPs and Haplotypes, Proceedings (Prepint), Carnegie Mellon University, Pittsburgh 2004

SP 1

OP 11

AB The paper addresses the combinatorial problem of inferring the unknown haplotypes in a population, given a sample of genotypes, under the assumption that the population forms
a perfect phylogeny (PP). It is important because physical haplotyping by DNA sequencing is expensive, whereas
genotypes are easier to obtain. Since PPs appear naturally and quite frequently, PP haplotyping is a favourable approach to reliable haplotype inference. Since Gusfield's paper from 2002, a few different algorithms have been proposed. Here we show that an extremely simple algorithm identifies, under the random mating assumption, all sufficiently frequent haplotypes in a random sample of
genotypes of asymptotically optimal size. Missing data can also be recovered if they are not too prevalent. Moreover, the idea of the algorithm easily extends to more general population structures than PP. We also solve a problem we call almost 2-coloring of graphs, which arises in an enhanced version of our haplotyping algorithm. We show that the solution space of this graph problem can be computed in linear time.

LA eng

OL 30