Machine Learning and Natural Language Processing Lab

Master Thesis

Flexible String Mining in Molecular Biology

Tanja Elas, 2005

---

Das Ziel meiner Diplomarbeit bestand darin, die bereits existierenden Algorithmen VST und FAVST in verschiedenen Bereichen zu erweitern und flexibler zu gestalten. Zum einen sollte die erzeugte Ergebnismenge verringert werden um so teilweise eine manuelle Inspektion der Muster zu ermoeglichen. Zum anderen wurden die bestehenden Arbeiten um die Moeglichkeit einer approximativen Suche erweitert. Bei der Entwicklung der neuen Algorithmen wurden zwei Ansaetze verfolgt: Zum einen sollte es dem Benutzer ermoeglicht werden den Mining Prozess entsprechend seiner Interessen bzw. seines Wissens zu steuern. Dies wird mit dem Algorithmus REDescend umgesetzt. Bei REDescend kann der Benutzer als Pradikat die Konjunktion einer minimalen Haeufigkeit und eines regularen Ausdrucks spezifizieren. Dies ist vor allem fuer selektive Benutzer von Vorteil, die schon ungefaehr wissen, welche Muster von Interesse sein koennen. Ausserdem wurde in dieser Diplomarbeit ein informations-theoretischer Ansatz verfolgt, indem das System und nicht der Benutzer Muster entfernt, die keine zusaetzliche Information enthalten. Der Algorithmus CLOSEST baut einen Version Space Tree mittels Tiefensuche auf und ermittelt wahrenddessen die haeufigen und geschlossenen Muster. Der grosse Vorteil dieses Verfahrens besteht darin, dass bei der Haeufigkeitszahlung nicht wiederholt die gesamte Datenbank durchlaufen werden muss. Der dritte Teil dieser Arbeit beschaftigt sich mit approximativen Auftreten von Mustern. Die Suche nach "exakten" Vorkommen stellt in realen Anwendungen oft ein Problem dar, da diese seltener auftreten. Dies beginnt bei der Textverarbeitung (z.B. Tippfehler) und reicht bis zu Nukleotidsequenzen in der Molekularbiologie, die im Laufe der Evolution viele Arten von Mutationen unterworfen sind. Deswegen wurden in dieser Arbeit Algorithmen entwickelt, die es ermoeglichen approximative Vorkommen zu beruecksichtigen. Die Vorgehensweise des Algorithmus EDDescend ist analog zu Descend. Der Unterschied besteht im Zahlen approximativer Muster. Es wurde ein Distanzmass definiert, um Vorkommen zu zahlen, die innerhalb einer gegebenen maximalen zulassigen Distanz zum betrachteten Muster liegen. Der Vorteil dieses Verfahrens besteht in dessen Flexibilitat wobei jedoch auch ein Nachteil auftritt. Dieser besteht in der grossen Zahl gefundener Muster. Bei EDAscend, einem auf Ascend basierendem Algorithmus werden ebenfalls approximative Vorkommen gefunden. EDAscend wird allerdings zum Pruning genutzt, um die Anzahl der (z.B. durch Descend) gefundenen Muster zu reduzieren. Diese Algorithmen wurden auf das Problem der Identifikation von Bindestellen in DNA-Sequenzen angewendet.