Anwendungsorientierte Indexstrukturen für Approximate Pattern Matching

• Applicant: Professor Dr. Ernst W. Mayr
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2010
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 47837877

In vielen Anwendungen der Informatik (insbesondere in der Bioinformatik) ist es erforderlich, in Texten effizient nach den Vorkommen eines Teilwortes oder Musters zu suchen. Um beispielsweise auch Rechtschreibfehler oder Genmutationen zu berücksichtigen, ist es oft außerdem notwendig, dass nicht nur exakte, sondern fehlerbehaftete Treffer gefunden werden. Diese Problemstellung heißt Approximate Pattern Matching. Bei den Lösungsansätzen klafft eine große Lücke zwischen Theorie und Praxis, die mit diesem Projekt geschlossen werden soll, unter Anwendung des gesamten Spektrums des Algorithm-Engineering-Prozesses. In der ersten Förderperiode haben wir daher einen Instanzgenerator für reale und synthetische Testdaten entworfen und implementiert, sowie Algorithmen und Datenstrukturen für fehlertolerante Mustersuche implementiert. In der folgenden Förderperiode werden die verschiedenartigen Ansätze systematisch experimentell untersucht und verglichen. Die Algorithmen und Datenstrukturen werden dabei in einer Algorithmenbibliothek mit einer einheitlichen Schnittstelle zusammengefasst. Sie sollen insbesondere im Hinblick auf folgende Gesichtspunkte entworfen und optimiert werden: Cache-Effizienz, Verhalten im Sekundärspeicher sowie verteilte Datenstrukturen. Die Algorithmenbibliothek soll auch anderen Wissenschaftlern effiziente Verfahren zur fehlertoleranten, indexbasierten Mustersuche zur Verfügung stellen. Anwendungen sind beispielsweise das Suchen von Genen im menschlichen Genom, die mit Krankheiten in Verbindung stehen, oder auch die Plagiatserkennung bei Dokumenten.

• DFG Programme: Priority Programmes
• Subproject of: SPP 1307: Algorithm Engineering