SciDok

Eingang zum Volltext in SciDok

Lizenz

Dissertation zugänglich unter
URN: urn:nbn:de:bsz:291-scidok-52973
URL: http://scidok.sulb.uni-saarland.de/volltexte/2013/5297/


Genome signature based sequence comparison for taxonomic assignment and tree inference

Sequenzvergleich mit Hilfe der Genomsignatur für die taxonomische Einordnung von Sequenzen und das Lernen taxonomischer Bäume

Patil, Kaustubh Raosaheb

pdf-Format:
Dokument 1.pdf (5.459 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
SWD-Schlagwörter: DNS-Sequenz , Metagenom , Maschinelles Lernen , Klassifikation , Taxonomie
Freie Schlagwörter (Englisch): DNA-sequence , metagenome , machine learning , classification , taxonomy
Institut: Fachrichtung 6.2 - Informatik
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Hauptberichter: McHardy, Alice Carolyn (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 29.05.2013
Erstellungsjahr: 2013
Publikationsdatum: 05.06.2013
Kurzfassung auf Englisch: In this work we consider the use of the genome signature for two important bioinformatics problems; the taxonomic assignment of metagenome sequences and tree inference from whole genomes. We look at those problems from a sequence comparison point of view and propose machine learning based methods as solutions. For the first problem, we propose a novel method based on structural support vector machines that can directly predict paths in a tree implied by evolutionary relationships between taxa. The method is based on an ensemble strategy to predict highly specific assignments for varying length sequences arising from metagenome projects. Through controlled experimental analyses on simulated and real data sets we show the benefits of our method under realistic conditions.
For the task of genome tree inference we propose a metric learning method. Based on the assumption that for different groups of prokaryotes, as defined by their phylogeny, genomic or ecological properties, different oligonucleotide weights can be more informative, our method learns group-specific distance metrics. We show that, indeed, it is possible to learn specific distance metrics that provide improved genome trees for the groups.
In the outlook, we expect that for the addressed problems the work of this thesis will complement and in some cases even outperform alignment-based sequence comparison at a considerably reduced computational cost, allowing it to keep up with advancements in sequencing technologies.
Kurzfassung auf Deutsch: In dieser Arbeit wird die Verwendung der Genomsignatur für zwei wichtige bioinformatische Probleme untersucht. Diese sind zum einen die taxonomische Einordnung von Sequenzen aus Metagenomexperimenten und zum anderen das Lernen eines taxonomischen Baums aus verschiedenen ganzen Genomen. Diese beiden Probleme werden aus dem Blickwinkel der Sequenzanalyse betrachtet und Verfahren des maschinellen Lernens werden als Lösungsansätze vorgeschlagen. Für die Lösung des ersten Problems schlagen wir eine neue Methode vor, die auf strukturellen Support Vektor Maschinen beruht und direkt Pfade in einem Baum vorhersagen kann, der auf den evolutionären Ähnlichkeiten der Taxa beruht. Die Methode basiert auf einer Ensemble Strategie, um sehr genaue Zuweisungen für Sequenzen verschiedener Länge, die in Metagenomprojekten gemessen wurden, vorherzusagen. Wir zeigen die Vorteile unserer Methode auf simulierten sowie auf experimentellen Daten.
Für das zweite Problem, bei dem ein taxonomischer Baum, basierend auf der genetischen Sequenz gelernt werden soll, schlagen wir eine Methode vor, die eine Metrik lernt. Die Annahme, auf der diese Methode beruht, ist, dass für verschiedene Gruppen von Prokaryoten unterschiedliche Gewichtungen der Oligonukleotidvorkommen notwendig sind, weswegen eine gruppenspezifische Metrik gelernt wird. Die Gruppen können dabei aufgrund ihrer phylogenetischen Beziehungen oder ökologischer sowie genomischer Merkmale bestimmt sein. Wir zeigen in unserer Analyse, dass es hierdurch möglich ist, spezifische Metriken zu lernen, die zu besseren Bäumen für diese Gruppen führen.
Wir erwarten, dass unsere hier vorgestellten Arbeiten für die bearbeiteten Probleme Alignment-basierte Ansätze ergänzen und teilweise sogar überbieten können, wobei unsere Lösungen deutlich weniger Rechenzeit benötigen und damit mit dem rasanten Wachstum im Sequenzierbereich schritthalten können.
Lizenz: Veröffentlichungsvertrag für Dissertationen und Habilitationen

Home | Impressum | Über SciDok | Policy | Kontakt | Datenschutzerklärung | English