Representation learning for variable-sized multiple sequence alignments

Abstract

Multiple Alignments bilden die Grundlage für die Lösung zahlreicher essentieller Probleme in der Biologie, die von der Untersuchung bestimmter Krankheiten bis hin zu einem besseren Verständnis für die Evolution des Lebens reichen. Viele dieser Probleme stammen aus dem Forschungsbereich der Phylogenetik, welche versucht, die evolutionären Beziehungen zwischen biologischen Entitäten zu ermitteln. Die Inferenz von Phylogenien aus multiplen Alignments ist ein Problem mit hoher Komplexität, und bleibt trotz der Verwendung von Heuristiken bei großen Alignments nicht effizient lösbar. Der starke Anstieg erfolgreicher Anwendungen des maschinellen Lernens auf Probleme in der Evolutionsbiologie gibt Anlass zur Hoffnung, dieses Problem mit Hilfe datengesteuerter Lernansätze lösen zu können. Da die meisten maschinellen Lernalgorithmen einer Größenbeschränkung unterliegen, stellt die Berechnung numerischer Repräsentationen fixer Größe für beliebig große multiple Alignments einen entscheidenden ersten Schritt dar. In dieser Arbeit stellen wir ein zeitlich effizientes Framework vor, das semantisch aussagekräftige Repräsentationen fixer Größe für beliebig große multiple Alignments erzeugt, die für Aufgaben im Bereich der phylogenetischen Inferenz geeignet sind. Das Framework verwendet Graph Neural Networks, um Inputs variabler Größe verarbeiten zu können, und umfasst drei Module: Die (1) Transformation eines Alignments in seine entsprechende Graphen-Repräsentation, das (2) Embedding dieses Graphen, um seine Repräsentation fixer Größe zu berechnen, und das (3) Trainingsverfahren mittels Similarity Learning. Zu diesem Zweck führen wir einen Begriff der Semantik für Alignments ein, der erfordert, dass ähnliche Alignments nahe beieinander und unähnliche Alignments weit voneinander entfernt im Embedding-Raum liegen. Wir evaluieren das Framework empirisch anhand der phylogenetischen Aufgabe der Selektion des Modells der Sequenzevolution. Unsere Ergebnisse zeigen, dass wir in der Lage sind, semantisch sinnvolle Repräsentationen fixer Größe für beliebig große Alignments für bis zu vier verschiedene Modelle der Sequenzevolution zu lernen. In einer Benchmark-Studie bewerten wir weiters, ob die erzeugten Repräsentationen für nachfolgende Klassifikationsaufgaben geeignet sind, und vergleichen das Framework mit etablierten Methoden für die Modellauswahl. Wir kommen zu dem Schluss, dass unser Framework mit den etablierten Methoden in Bezug auf die Auswahl des Modells der Sequenzevolution konkurrenzfähig ist.

Multiple sequence alignments form the basis to address numerous fundamental problems arising in biology, ranging from the study of certain diseases to gaining a better understanding of the evolution of life itself. Many such problems stem from the research field of phylogenetics, which aims to infer the evolutionary relationships among a set of biological entities. Inferring phylogenies from multiple sequence alignments is a hard task, which, despite resorting to heuristics, remains computationally inefficient for large alignments. The recent surge in successful applications of machine learning to problems in evolutionary biology gives hope to overcome this issue by means of data-driven learning approaches. As most machine learning algorithms are subject to a size constraint of some kind, the computation of numerical, fixed-size representations for arbitrarily sized multiple sequence alignments constitutes a crucial first step. In this thesis, we introduce a polynomial-time framework which produces semantically meaningful representations of fixed size, suitable for tasks related to phylogenetic inference, for variable-sized multiple sequence alignments. The framework employs graph neural networks to handle variable-sized input and comprises three modules for the (1) transformation of an alignment into its corresponding graph representation, the (2) embedding of this graph to compute its fixed-size representation, and the (3) training procedure by means of similarity learning. For this purpose, we introduce a notion of semantics for alignments which necessitates similar alignments to be close to, and dissimilar alignments to be distant from each other in the embedding space. We empirically evaluate the framework on the phylogenetic task of the selection of the model of sequence evolution. Our results indicate that we are able to learn semantically meaningful representations of fixed size for arbitrarily sized alignments for up to four different models of sequence evolution. We further assess whether the produced representations are suitable for subsequent classification tasks in a benchmark study, where we compare the framework with established methods for the task of model selection. We conclude that our framework is competitive with the established methods with respect to the selection of the model of sequence evolution.