RegEx Anfragen für biologische Sequenzen (RegExBis)

• Antragsteller: Professor Dr. Knut Reinert; Professor Dr. Matthias Weidlich
• Fachliche Zuordnung: Datenmanagement, datenintensive Systeme, Informatik-Methoden in der Wirtschaftsinformatik ; Bioinformatik und Theoretische Biologie
• Förderung: Förderung seit 2025
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 541107382

DNA Sequenzierung, d.h. die Bestimmung der linearen Abfolge von Nukleotiden in der DNA eines Individuums, ist eine grundlegende Technologie in der Biology. Die Technologie erlaubt es, Variationen in Genen zu bestimmen sowie diese zu Phenotypen oder bestimmten Krankheiten zu verlinken. Bedingt durch die zahlreichen Anwendungen hat die Sequenzierungstechnologie unglaubliche Fortschritte in den letzten 10 Jahren gemacht. Eine einzige, durchschnittliche Maschine für günstiges Next-generation Sequencing (NGS) kann ca 400 Milliarden Basenpaare pro Tag lesen, was dazu führt, dass die Größe der DNA und Proteindatenbanken exponentiell wächst. Die Analyse dieser Daten beruht zu großen Teilen auf Anfragen die eine spezifische Anordnung von Nukleotiden oder Aminosäuren in diesen großen Datenbanken findet. Traditionelle Analysen suchen die Ergebnisse eines Sequenzierungsexperimentes (read) mit Hilfe von Techniken des approximativen String matchings. Dabei wird nicht die komplette Datenbank durchsucht, sondern Indizierungsmethoden basierend auf Volltext-Indices oder k-meren benutzt. Dieses Projekt zielt darauf ein komplexeres Problem zu lösen, nämlich wie man große Datenbanken mit komplexeren Anfragen durchsuchen kann. Anwendungen wie die Suche in Proteon Familien in der PROSITE Datenbank oder das Finden von TFBS (transcription factor binding sites) brauchen komplexere Anfragenmöglichkeiten, die man durch (erweiterte) reguläre Ausdrücke beschreiben kann, die Wildcards, Disjunktion, Gruppierungen und Quantifizierer (Kleene star, min oder max Vorkommen) beschreiben kann. Es gibt bereits einige Implementierungen für das Suchen von regulären Ausdrücken, die aber oft heuristischer Natur sind, wie z.B. PHI-Blast. Diese brauchen bereits Sekunden für eine Anfrage auf einer recht kleinen Datenbank und skalieren nicht. Das Projekt "Reg Ex Querying of Biological Sequences" möchte die Grundlagen für eine effiziente Implementierung von (erweiterten) regulären Ausdrücken in sehr großen Sequenzdatenbanken legen indem es die folgenden Forschungsfragen betrachtet: * Welche Repräsentierung von Sequenzen erlaubt ein effizientes Filtern von Datenbanken für Regex Anfragen? * Wie können wir formelle Fehlerschranken für die approximative Suche von Regex Anfragen zeigen? * Wie können wir die Datenstrukturen (semi-)dynamisch machen? Um diese Fragen zu beantworten wählen wir einen interdisziplinären Ansatz. Wir adaptieren uns auf der einen Seite Methoden welche erfolgreiche Filter für appoximative Suchen implementieren und verbinden dies mit Resultaten bzgl. der Dekomposition von regex Anfragen die für complex event recognition entwickelt wurden. Darüberhinaus benutzen wir Ideen für das soft clustering von Datenbanken. Insofern erwarten wir, dass die Ergebnisse des Projektes einen Einfluss auf alle drei Forschungsfelder haben werden.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Israel
• ausländischer Mitantragsteller: Professor Dr.-Ing. Avigdor Gal, Ph.D.