Anwendungsorientierte Indexstrukturen für Approximate Pattern Matching

• Antragsteller: Professor Dr. Ernst W. Mayr
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2007 bis 2010
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 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-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1307: Algorithm Engineering