CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Fast perfect phylogeny haplotype inference

Peter Damaschke (Institutionen för datavetenskap, Algoritmer ; Institutionen för datavetenskap, Bioinformatik)
Lecture Notes in Computer Science. 14th International Symposium on Fundamentals of Computation Theory FCT'2003, Malmö, 12-15 August 2003 (0302-9743). Vol. 2751 (2003), p. 183-194.
[Konferensbidrag, refereegranskat]

We address the problem of reconstructing haplotypes in a population, given a sample of genotypes and assumptions about the underlying population. The problem is of major interest in genetics because haplotypes are more informative than genotypes when it comes to searching for trait genes, but it is difficult to get them directly by sequencing. After showing that simple resolution-based inference can be terribly wrong in some natural types of population, we propose a different combinatorial approach exploiting intersections of sampled genotypes (considered as sets of candidate haplotypes). For populations with perfect phylogeny we obtain an inference algorithm which is both sound and efficient. It yields with high propability the complete set of haplotypes showing up in the sample, for a sample size close to the trivial lower bound. The perfect phylogeny assumption is often justified, but we also believe that the ideas can be further extended to populations obeying relaxed structural assumptions. The ideas are quite different from other existing practical algorithms for the problem.



Denna post skapades 2006-09-25. Senast ändrad 2015-02-11.
CPL Pubid: 1741

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för datavetenskap, Algoritmer (2002-2004)
Institutionen för datavetenskap, Bioinformatik (2002-2004)

Ämnesområden

Information Technology

Chalmers infrastruktur