50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Komplexität von Haplotypisierungsproblemen


Projektbeschreibung

Projektname
Komplexität von Haplotypisierungsproblemen
Leitung
Prof. Dr. Till Tantau
Laufzeit und Drittmittelgeber
Beginn 2005, voraussichtliches Ende 2010. Förderung durch die DFG.
Projektmitarbeiter
Ilka Schnoor, Michael Elberfeld, Jakob Kuczewski, Jannis Pohlmann
Zusammenfassung
Einer der nächsten Schritte in der Erforschung des menschlichen Genoms wird die Erstellung der Haplotypenkarte sein. Sie wird aufzeigen, welche Beziehungen zwischen den Haplotypen (Variationen in der DNS-Sequenz) eines Individuums und der Wahrscheinlichkeit bestehen, auf bestimmte Medikamente anzusprechen oder bestimmte Krankheiten zu bekommen. Kostengünstige und schnelle Verfahren zur individuellen Haplotypenbestimmung werden große Bedeutung für Vorsorge- und Behandlungsplanung haben. Gängige Verfahren liefern allerdings lediglich Genotypen, die zwar alle Informationen über die Variation der DNS-Sequenz an verschiedenen Stellen enthalten, bei denen aber die Zuordnung zu den beiden Chromosomsträngen verlorengegangen ist. Unter (praktisch belegten) evolutionstheoretischen Annahmen lassen sich Haplotypen aus Genotypdaten kombinatorisch rekonstruieren, man spricht vom Haplotypisierungsproblem. Die Berechnungskomplexität dieses Problems soll in Abhängigkeit von den gemachten Annahmen klassifiziert werden, um algorithmisch hilfreiche Annahmen zu identifizieren. Lösungsalgorithmen (beziehungsweise Approximations- oder Fixed-Parameter-Algorithmen) sollen weiterentwickelt und neue Ansätze erprobt werden. Die Tauglichkeit der Algorithmen soll mittels öffentlich zugänglicher Genotypdaten validiert und verglichen werden. Kernziel ist ein Algorithmus zur Haplotypisierung, der bei in der Praxis zutreffenden Annahmen effizient arbeitet und der die Haupteinschränkung aller bekannten Verfahren überwindet: das bei der Genotypbestimmung unvermeidliche Fehlen von Daten. Förderung durch die DFG seit November 2005.

Projektentwicklungen

Im Rahmen des Projektes wurde eine Softwarebibliothek entwickelt (nur in Englisch verfügbar).

Projektveröffentlichungen

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.
    PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen
  • Michael Elberfeld, Till Tantau:
    Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
    Information and Computation, 213:33–47, 2012.
    PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen

2010

  • Michael Elberfeld, Till Tantau:
    Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
    Technischer Bericht SIIM-TR-A-10-01, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2010.
    PDF anzeigen | Zusammenfassung anzeigen
  • 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), Band 6129 von Lecture Notes in Computer Science, S. 177-189. Springer, 2010.
    Website anzeigen | Zusammenfassung anzeigen

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), Band 5532 von Lecture Notes in Computer Science, S. 201-210. Springer, 2009.
    PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen
  • Michael Elberfeld:
    Perfect Phylogeny Haplotyping is Complete for Logspace.
    Technischer Bericht abs/0905.0602 [cs.CC], Computing Research Repository (CoRR), 2009.
    Website anzeigen | Zusammenfassung anzeigen
  • 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.
    Website anzeigen | Zusammenfassung anzeigen

2008

  • Jens Gramm, Arfst Nickelsen, Till Tantau:
    Fixed-Parameter Algorithms in Phylogenetics.
    In Bioinformatics: Volume I: Data, Sequence Analysis and Evolution, Band 452 von Methods in Molecular Biology, S. 507-535. Springer, 2008.
    Zusammenfassung anzeigen
  • Michael Elberfeld, Till Tantau:
    Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems.
    Technischer Bericht SIIM-TR-A-08-02, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2008.
    PDF anzeigen | Zusammenfassung anzeigen
  • 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), Band 5162 von Lecture Notes in Computer Science, S. 299-310. Springer, 2008.
    Website anzeigen | Zusammenfassung anzeigen
  • Michael Elberfeld, Ilka Schnoor, Till Tantau:
    Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data.
    Technischer Bericht SIIM-TR-A-08-05, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2008.
    PDF anzeigen | Zusammenfassung anzeigen
  • Jens Gramm, Arfst Nickelsen, Till Tantau:
    Fixed-Parameter Algorithms in Phylogenetics.
    The Computer Journal, 51(1):79--101, 2008.
    PDF anzeigen | Zusammenfassung anzeigen

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.
    Zusammenfassung anzeigen

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), Band 4175 von Lecture Notes in Computer Science, S. 92-102. Springer, 2006.
    Zusammenfassung anzeigen

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, S. 35-46. , 2004.
    Zusammenfassung anzeigen
  • 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, Band 3162 von Lecture Notes in Computer Science, S. 174-186. Springer, 2004.
    Zusammenfassung anzeigen