Das Paper "Analysis of min-hashing for variant tolerant DNA read mapping" von Jens Quedenfeld (jetzt TU München) und Sven Rahmann wurde mit dem Best Paper Award auf dem Workshop für Algorithmen in der Bioinformatik (WABI) 2017, veranstaltet in Camebridge MA, USA 20-23 August, ausgezeichnet.

Die Autoren stellen bezüglich des DNA Read Mapping, einer allgegenwärtigen Aufgabe in der Bioinformatik, eine wichtige Frage. Neue Technologien stellen immer längere DNA Sequenzen (mehrere Tausend Basenpaare) mit allerdings größeren Fehlerraten (bis zu 15%) zur Verfügung. Das Referenzgenom wird dabei des Öfteren nicht mehr als einfacher ACGT-String interpretiert sondern, als komplexes Objekt, das genetische Varianten innerhalb der Bevölkerung enthält. Konventionelle Indizes basierend auf exakten Seed Matches, vor allem der auf dem Suffix Array basierende FM Index, haben Probleme sich den verändernden Umständen anzupassen. Dementsprechend wurden andere Methoden erwägt und eine solche ist Locality Sensitive Hashing. Bei dieser Methode untersuchen wir die Problemstellung ob das Hinzufügen von Single Nucleotide Polymorphisms (SNPs) in einem Min-Hashing Index vorteilhaft ist. Die Antwort hängt von der Population Frequency des SNPs ab. Wir analysieren mehrere Modelle (von einfach bis komplex), die präzise Antworten, bedingt durch mehrere Annahmen, liefern. Unsere Ergebnisse enthalten zusätzlich sensitivitäts und spezifitäts-Werte für die auf dem Min-Hashing basierenden Read Mappers. Diese Ergebnisse können benutzt werden um Abhängigkeiten zwischen Parametern dieser Methoden zu verstehen. Das Paper kann eine neue Grundlage für eine neue Generation von Read Mappern darstellen.

Das Paper ist auf den WABI Conference Proceedings (Proceedings of the 17th International Workshop on Algorithms in Bioinformatics(WABI 2017), Russel Schwartz and Knut Reinert (Eds.), LIPICS Vol.88) frei zugänglich.

Diese Arbeit ist Teil des Teilprojektes C1.