50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Complexity of Haplotyping Problems


Project Description

Project name
Complexity of Haplotyping Problems
Leadership
Prof. Dr. Till Tantau
Duration and Funding
Started 2005, estimated completion in 2010. Supported by the DFG.
Project staff
Ilka Schnoor, Michael Elberfeld, Jakob Kuczewski, Jannis Pohlmann
Abstract
One of the next steps in human genome research will be the construction of the haplotype map. It will show which relationships exists between an individual's haplotypes (variations of the DNA-structure) and the indiviual's likelihood to react to a specific drug or to get a specific desease. Simple, inexpensive technology for determining an individual's haplotypes will become important both in medical treatment and screening. Current technology only allows us to quickly determine the genotypes of individuals. Genotypes contain all information about the genetic variations of an individual at sites of interest, but the mapping of the variations to the two chromosomes is lost. Under certain evolution-theoretic assumptions it is nevertheless possible to reconstruct the haplotypes from the genotypes. This reconstruction problem is called the haplotyping problem.

Project System Development

A software library was developped for this project.

Project Publications

2012

  • Michael Elberfeld, Ilka Schnoor, Till Tantau:
    Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data.
    Theoretical Computer Science, 432:38–51, 2012.
    Show PDF | Go to website | Show abstract
  • Michael Elberfeld, Till Tantau:
    Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
    Information and Computation, 213:33–47, 2012.
    Show PDF | Go to website | Show abstract

2010

  • Michael Elberfeld, Till Tantau:
    Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
    Technical report SIIM-TR-A-10-01, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2010.
    Show PDF | Show abstract
  • Michael Elberfeld, Till Tantau:
    Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
    In Proceedings of the 21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010), Volume 6129 of Lecture Notes in Computer Science, pp. 177-189. Springer, 2010.
    Go to website | Show abstract

2009

  • Michael Elberfeld, Ilka Schnoor, Till Tantau:
    Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data.
    In Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation (TAMC 2009), Volume 5532 of Lecture Notes in Computer Science, pp. 201-210. Springer, 2009.
    Show PDF | Go to website | Show abstract
  • Michael Elberfeld:
    Perfect Phylogeny Haplotyping is Complete for Logspace.
    Technical report abs/0905.0602 [cs.CC], Computing Research Repository (CoRR), 2009.
    Go to website | Show abstract
  • Jens Gramm, Tzvika Hartman, Till Nierhoff, Roded Sharan, Till Tantau:
    On the complexity of SNP block partitioning under the perfect phylogeny model.
    Discrete Mathematics, 309(18):5610-5617, 2009.
    Go to website | Show abstract

2008

  • Jens Gramm, Arfst Nickelsen, Till Tantau:
    Fixed-Parameter Algorithms in Phylogenetics.
    In Bioinformatics: Volume I: Data, Sequence Analysis and Evolution, Volume 452 of Methods in Molecular Biology, pp. 507-535. Springer, 2008.
    Show abstract
  • Michael Elberfeld, Till Tantau:
    Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems.
    Technical report SIIM-TR-A-08-02, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2008.
    Show PDF | Show abstract
  • Michael Elberfeld, Till Tantau:
    Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems.
    In Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008), Volume 5162 of Lecture Notes in Computer Science, pp. 299-310. Springer, 2008.
    Go to website | Show abstract
  • Michael Elberfeld, Ilka Schnoor, Till Tantau:
    Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data.
    Technical report SIIM-TR-A-08-05, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2008.
    Show PDF | Show abstract
  • Jens Gramm, Arfst Nickelsen, Till Tantau:
    Fixed-Parameter Algorithms in Phylogenetics.
    The Computer Journal, 51(1):79--101, 2008.
    Show PDF | Show abstract

2007

  • Jens Gramm, Till Nierhoff, Roded Sharan, Till Tantau:
    Haplotyping with Missing Data via Perfect Path Phylogenies.
    Discrete and Applied Mathematics, 155:788-805, 2007.
    Show abstract

2006

  • Jens Gramm, Tzvika Hartman, Till Nierhoff, Roded Sharan, Till Tantau:
    On the Complexity of SNP Block Partitioning Under the Perfect Phylogeny Model.
    In Proceedings of Workshop on Algorithms in Bioinformatics (WABI), Volume 4175 of Lecture Notes in Computer Science, pp. 92-102. Springer, 2006.
    Show abstract

2004

  • Jens Gramm, Till Nierhoff, Roded Sharan, Till Tantau:
    On the Complexity of Haplotyping via Perfect Phylogeny.
    In Proceedings of Second RECOMB Satellite Workshop on Computational Methods for SNPs and Haplotypes, pp. 35-46. , 2004.
    Show abstract
  • Jens Gramm, Till Nierhoff, Till Tantau:
    Perfect Path Phylogeny Haplotyping with Missing Data is Fixed-Parameter Tractable.
    In Proceedings of the 2004 International Workshop on Parameterized and Exact Computation, Volume 3162 of Lecture Notes in Computer Science, pp. 174-186. Springer, 2004.
    Show abstract