TU Darmstadt / ULB / TUbiblio

Visual Search and Analysis in Molecular Biology

Heß, Martin Philipp (2018)
Visual Search and Analysis in Molecular Biology.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

The computation of protein sequence alignments is one of the most fundamental tasks in computational biology. Pairwise sequence alignments (PSA) form the basis for the detection of homologous protein sequences. Multiple sequence alignments (MSA) can provide insights into structural and functional relationships across a set of proteins. In the alignment process, evolutionary, functionally, or structurally related regions between the sequences are identified and aligned depending on a particular scoring model. Evolutionary substitution events are usually modeled by substitution matrices, while insertion and deletion events are modeled by specific gap penalties.

The quality of sequence alignments depends heavily on the chosen scoring model, the alignment algorithm, and the sequence data itself. The selection of the best parameters for a given alignment task is, however, non-trivial. Thus many researchers regularly use potentially suboptimal default parameters. This also includes biased and dated substitution matrices. In addition, the construction of MSAs is an NP-complete task and as such the optimal alignment is unknown, even for a fixed parameter set. MSA algorithms thus rely on heuristics to approximate the optimal MSA resulting in alignments of suboptimal quality which often require manual refinement. Assessing the quality of MSAs is also problematic since most established quality measures are limited in the detection of bad alignment regions.

In this thesis, we present several approaches and concepts to improve the accuracy of sequence alignments. In particular, this includes two novel substitution models to enable existing methods to produce better alignments as well as approaches to enable experts and non-experts to assess the quality of the computed MSAs and to effectively refine them to improve their accuracy.

We present the novel CorBLOSUM substitution model that fixes a substantial programming error in the original BLOSUM code. This error negatively affects the homologous sequence search performance of the original BLOSUM matrices as well as their revised RBLOSUM variants. Our exhaustive benchmark analysis based on 51 different ASTRAL subsets shows that CorBLOSUM matrices usually detect more true homologs when compared with their incorrect BLOSUM and RBLOSUM counterparts. For this reason, using CorBLOSUM matrices instead of BLOSUM can substantially improve the results of homologous sequence search.

Furthermore, we propose the novel PFASUM substitution model that is derived from Pfam seed alignments using our novel PFASUM algorithm. Unlike conventional substitution models, our PFASUM matrices are thus based on manually curated expert ground truth data that reflects the currently known sequence space. Additionally, our PFASUM algorithm incorporates several mechanism to avoid oversampling while handling ambiguous amino acids in a reasonable way. As shown by our thorough performance evaluations, these features enable PFASUM matrices to significantly outperform widely used conventional matrices in homologous sequence search. Additionally, using PFASUM matrices for the construction of MSAs also results in more accurate MSAs in most cases.

Beside the aforementioned substitution models, we present a novel visual analysis and comparison approach for protein MSAs. It allows to detect reliably aligned and misaligned regions in protein MSAs without much effort. This is achieved by using an automatic comparison of alternative MSAs of the same sequence set and the visualization of consistently aligned regions and uncertain areas in the MSAs. Our evaluation shows that our system allows to successfully assess the accuracy of MSAs and to effectively determine uncertain regions for further refinement. Additionally, it can be used to visually assess the impact of different alignment algorithms and parameterizations on the resulting alignments.

In order to outsource the cumbersome task of manual MSA refinement, we present our scientific discovery game Bionigma. It abstracts the alignment problem in the form of a puzzle game. In these puzzles, the amino acids in the alignment are represented by different game tokens. Like one would align beads of identical color in an abacus, the players must align similar tokens to improve their score. Through this, the players successively refine the real MSA in a playful manner. Several user studies show that Bionigma is fun to play and delivers a true game experience to the players. Additionally, our results demonstrate that casual players can successfully refine protein MSAs. In particular, they can even produce more accurate than automatic methods.

In summary, the here presented approaches and concepts can help to significantly improve the accuracy of protein sequence alignments. Notably, our methods enable biologists without profound knowledge in the field of sequence alignments to generate better results without much effort.

Typ des Eintrags: Dissertation
Erschienen: 2018
Autor(en): Heß, Martin Philipp
Art des Eintrags: Erstveröffentlichung
Titel: Visual Search and Analysis in Molecular Biology
Sprache: Englisch
Referenten: Goesele, Prof. Dr. Michael ; Weigt, Prof. Dr. Martin ; Hamacher, Prof. Dr. Kay
Publikationsjahr: 2018
Ort: Darmstadt
Datum der mündlichen Prüfung: 19 Dezember 2017
URL / URN: http://tuprints.ulb.tu-darmstadt.de/7306
Kurzbeschreibung (Abstract):

The computation of protein sequence alignments is one of the most fundamental tasks in computational biology. Pairwise sequence alignments (PSA) form the basis for the detection of homologous protein sequences. Multiple sequence alignments (MSA) can provide insights into structural and functional relationships across a set of proteins. In the alignment process, evolutionary, functionally, or structurally related regions between the sequences are identified and aligned depending on a particular scoring model. Evolutionary substitution events are usually modeled by substitution matrices, while insertion and deletion events are modeled by specific gap penalties.

The quality of sequence alignments depends heavily on the chosen scoring model, the alignment algorithm, and the sequence data itself. The selection of the best parameters for a given alignment task is, however, non-trivial. Thus many researchers regularly use potentially suboptimal default parameters. This also includes biased and dated substitution matrices. In addition, the construction of MSAs is an NP-complete task and as such the optimal alignment is unknown, even for a fixed parameter set. MSA algorithms thus rely on heuristics to approximate the optimal MSA resulting in alignments of suboptimal quality which often require manual refinement. Assessing the quality of MSAs is also problematic since most established quality measures are limited in the detection of bad alignment regions.

In this thesis, we present several approaches and concepts to improve the accuracy of sequence alignments. In particular, this includes two novel substitution models to enable existing methods to produce better alignments as well as approaches to enable experts and non-experts to assess the quality of the computed MSAs and to effectively refine them to improve their accuracy.

We present the novel CorBLOSUM substitution model that fixes a substantial programming error in the original BLOSUM code. This error negatively affects the homologous sequence search performance of the original BLOSUM matrices as well as their revised RBLOSUM variants. Our exhaustive benchmark analysis based on 51 different ASTRAL subsets shows that CorBLOSUM matrices usually detect more true homologs when compared with their incorrect BLOSUM and RBLOSUM counterparts. For this reason, using CorBLOSUM matrices instead of BLOSUM can substantially improve the results of homologous sequence search.

Furthermore, we propose the novel PFASUM substitution model that is derived from Pfam seed alignments using our novel PFASUM algorithm. Unlike conventional substitution models, our PFASUM matrices are thus based on manually curated expert ground truth data that reflects the currently known sequence space. Additionally, our PFASUM algorithm incorporates several mechanism to avoid oversampling while handling ambiguous amino acids in a reasonable way. As shown by our thorough performance evaluations, these features enable PFASUM matrices to significantly outperform widely used conventional matrices in homologous sequence search. Additionally, using PFASUM matrices for the construction of MSAs also results in more accurate MSAs in most cases.

Beside the aforementioned substitution models, we present a novel visual analysis and comparison approach for protein MSAs. It allows to detect reliably aligned and misaligned regions in protein MSAs without much effort. This is achieved by using an automatic comparison of alternative MSAs of the same sequence set and the visualization of consistently aligned regions and uncertain areas in the MSAs. Our evaluation shows that our system allows to successfully assess the accuracy of MSAs and to effectively determine uncertain regions for further refinement. Additionally, it can be used to visually assess the impact of different alignment algorithms and parameterizations on the resulting alignments.

In order to outsource the cumbersome task of manual MSA refinement, we present our scientific discovery game Bionigma. It abstracts the alignment problem in the form of a puzzle game. In these puzzles, the amino acids in the alignment are represented by different game tokens. Like one would align beads of identical color in an abacus, the players must align similar tokens to improve their score. Through this, the players successively refine the real MSA in a playful manner. Several user studies show that Bionigma is fun to play and delivers a true game experience to the players. Additionally, our results demonstrate that casual players can successfully refine protein MSAs. In particular, they can even produce more accurate than automatic methods.

In summary, the here presented approaches and concepts can help to significantly improve the accuracy of protein sequence alignments. Notably, our methods enable biologists without profound knowledge in the field of sequence alignments to generate better results without much effort.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

Die Konstruktion von Proteinsequenzalignments ist eine der fundamentalsten Aufgaben in der Bioinformatik. Paarweise Sequenzalignments (PSA) stellen beispielsweise die Basis für die Detektion homologer Proteinsequenzen. Multiple Sequenzalignments (MSA) erlauben es, Erkenntnisse über strukturelle und funktionale Zusammenhänge zwischen mehreren Protein zu gewinnen. In Abhängigkeit des gewählten Bewertungsmodells werden in einem Sequenzalignment entweder evolutionär, funktional oder strukturell verwandte Sequenzsegmente identifiziert und zueinander angeordnet. Dabei werden evolutionäre Substitutionsereignisse normalerweise durch sogenannte Substitutionsmatrizen modelliert. Insertions- und Deletionsereignisse werden hingegen durch Lücken im Alignment repräsentiert, die mit Strafpunkten bewertet werden.

Die Qualität eines Sequenzalignments hängt maßgeblich vom gewählten Bewertungsschema und Alignmentalgorithmus ab. Zusätzlich haben die Sequenzdaten selbst einen gewissen Einfluss auf die Qualität des Alignments. Da die Selektion dieser Parameter ein schwieriges Problem darstellt, verwenden viele Benutzer suboptimale Standardparameter, wie zum Beispiel ältere oder nachweislich durch Fehler beeinflusste Substitutionsmatrizen. Außerdem stellt die Berechnung von optimalen multiplen Sequenzalignments ein NP-vollständiges Optimierungsproblem dar. Dadurch ist die optimale Alignmentlösung selbst für ein fix gewähltes Parameterset unbekannt. Aus diesem Grund verwenden die meisten Alignmentalgorithmen Heuristiken um das optimale Alignment zu approximieren. Dies resultiert allerdings sehr häufig in suboptimalen Alignments, die manuell weiter verfeinert werden müssen. Leider ist auch die Qualitätsanalyse von MSAs nur sehr eingeschränkt möglich, da existierende Qualitätsmaße tatsächlich schlechte Alignmentregionen nur unzureichend detektieren können.

In dieser Arbeit präsentieren wir daher verschiedene Ansätze, um die Genauigkeit und Qualität von Protein MSAs zu verbessern. Hierfür stellen wir zwei neue Substitutionsmodelle vor, durch deren Verwendung bestehende Alignmentverfahren in der Lage sind, bessere Ergebnisse zu liefern. Zusätzlich stellen wir weitere Verfahren und Ansätze vor, um Experten als auch Nicht-Experten eine bessere Qualitätsanalyse als auch eine effektivere Möglichkeit zur Verfeinerung von MSAs zu bieten.

Hierzu stellen wir das neuartige CorBLOSUM Substitutionsmodell vor. Dieses Modell korrigiert einen Programmierfehler im originalen BLOSUM Programmcode, der sich negativ auf die Fähigkeiten zur homologen Sequenzsuche der BLOSUM als auch der RBLOSUM Matrizen auswirkt. Unsere Ergebnisse basierend auf einer umfassenden Performanzuntersuchung unter der Verwendung von 51 verschiedenen ASTRAL Datenbanken zeigen, dass CorBLOSUM Matrizen in der Regel mehr korrekte homologe Sequenzen detektieren können als die getesteten BLOSUM und RBLOSUM Matrizen. Aus diesem Grund können CorBLOSUM Matrizen substantiell dazu beitragen, bessere Ergebnisse in der homologen Sequenzsuche zu erzielen.

Darüber hinaus präsentieren wir in dieser Arbeit die neuartigen PFASUM Substitutionsmatrizen. Diese Matrizen werden auf Basis von Pfam seed alignments unter Verwendung eines neuartigen Algorithmus erzeugt. Im Gegensatz zu anderen Substitutionsmodellen basieren unsere PFASUM Substitutionsmatrizen somit auf manuell von Experten optimierten Daten, die den aktuell bekannten Proteinsequenzraum abbilden. Außerdem verwendet der PFASUM Algorithmus verschiedene Techniken, um Oversampling zu vermeiden und uneindeutige Aminosäuresymbole in den Alignments geeignet zu verarbeiten. Diese Eigenschaften erlauben es unseren PFASUM Matrizen, konventionelle Substitutionsmodelle in der Suche nach homologen Sequenzen zu übertreffen, wie unsere Studie belegt. Außerdem kann durch die Verwendung unserer PFASUM Matrizen zur Konstruktion von MSAs in den meisten Fällen eine höhere MSA Genauigkeit erzielt werden.

Weiterhin stellen wir einen neuartigen Ansatz zur visuellen Analyse und zum Vergleich von Protein MSAs vor. Mit diesem Ansatz ist es möglich, zuverlässige und falsch angeordnete Regionen in MSAs ohne großen Aufwand zu detektieren. Unser Verfahren nutzt hierzu automatische Vergleichsmaße und verschiedene Visualisierungen, um konsistent angeordnete und unsichere Alignmentregionen hervorzuheben. Unsere Ergebnisse zeigen, dass mit unserem Ansatz die Genauigkeit von MSAs erfolgreich bestimmt werden kann. Außerdem können hierdurch verbesserungswürdige Regionen in den Alignments zur weiteren Optimierung detektiert werden. Unser Ansatz erlaubt es zusätzlich, den Einfluss von verschiedenen Alignmentalgorithmen und Parametrisierungen auf die Struktur der Alignments zu untersuchen.

Um die aufwendige Aufgabe der manuellen Verfeinerung von MSAs auszulagern, stellen wir außerdem einen Computerspielansatz vor. Unser wissenschaftliches Erkundungsspiel Bionigma abstrahiert das Alignmentproblem in Form eines Puzzles. Die Aminosäuren in einem Alignment werden in diesen Puzzlen als Spielsteine repräsentiert. Durch die Anordnung von ähnlichen Spielsteinen, ähnlich dem Anordnen von bunten Perlen in einem Abakus, können die Spieler ihre Punktzahl erhöhen. Hierdurch wird auch das echte Alignment sukzessive verfeinert. Mehrere Benutzerstudien zeigen, dass Bionigma Spaß macht und seinen Spielern eine echte Spielerfahrung bietet. Außerdem zeigen unsere Ergebnisse, das Gelegenheitsspieler erfolgreich MSAs verfeinern und auch unter Umständen MSA Programme übertreffen können.

Zusammenfassend lässt sich sagen, dass die hier vorgestellten Verfahren signifikant zur Verbesserung der Genauigkeit von MSAs beitragen können. Durch unsere Ansätze können Biologen mit weniger profunden Kenntnissen auf dem Gebiet der Sequenzalignments bessere Ergebnisse ohne großen Aufwand erzielen.

Deutsch
URN: urn:nbn:de:tuda-tuprints-73062
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
500 Naturwissenschaften und Mathematik > 570 Biowissenschaften, Biologie
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
20 Fachbereich Informatik > Graphics, Capture and Massively Parallel Computing
Hinterlegungsdatum: 29 Jul 2018 19:55
Letzte Änderung: 29 Jul 2018 19:55
PPN:
Referenten: Goesele, Prof. Dr. Michael ; Weigt, Prof. Dr. Martin ; Hamacher, Prof. Dr. Kay
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 19 Dezember 2017
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen