RegEx Anfragen für biologische Sequenzen

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. Diese 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.