Direkt zum Inhalt | Direkt zur Navigation

Eingang zum Volltext

Lizenz

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:25-opus-81561
URL: http://www.freidok.uni-freiburg.de/volltexte/8156/


Mann, Martin

Computational Methods for Lattice Protein Models

Rechnerische Methoden für Gitterproteinmodelle

Dokument1.pdf (17.408 KB) (Dissertation in finaler Version) (md5sum: 4e0301f3596dba7bfdd947ddfc321318)

Kurzfassung in Englisch

Proteins are involved in almost all processes in living cells. They act as regulators, catalyzers, transporters, and in many other functions that are determined by their three-dimensional structures.

This thesis studies the fundamental concepts that define and guide the folding processes of proteins. Therein, the prediction of a protein's native fold as well as the modeling of its folding process are of great importance. To enable large scale studies, lattice protein models are used that are available at different levels of abstraction. Central to this thesis is the development and implementation of efficient methods to study proteins represented in complex three-dimensional lattices. A major focus is the development of procedures that enable the usage of more realistic side chain models.

An important task when studying protein models is the transfer of real protein structures into the model. This NP-complete problem is tackled in the first part of the thesis. A combination of efficient heuristics and constraint-based search yields models of high quality and low runtimes.

The second part of the thesis presents methods to determine minimum energy structures. Here, a constraint-based approach is introduced that for the first time makes it possible to predict energetically optimal structures within hydrophobic-polar~(HP) side chain models. This enables the first study of optimal structures within the model revealing an immense degeneracy. Since many structures cannot be distinguished by the energy function, an equivalence relation for the grouping of optimal structures is introduced. An extension of the constraint-based structure prediction approach enables the efficient and direct computation of the resulting equivalence classes. HP-optimal structures from different classes can be used for the initialization of local search methods that tackle more advanced energy functions. The superiority of such an approach compared to standard strategies is demonstrated.

In addition, to enable local search methods in side chain models, the definition and efficient implementation of a neighborhood relation between structures is needed. The third part of the thesis covers the presentation of an interval-based local neighborhood relation for arbitrary lattices. An efficient procedure for the enumeration of neighbored structures opens the door for new studies in side chain lattice protein models.

Subsequently, the phenomenon of co-translational folding is explored, i.e. the folding of the emerging protein while it is assembled at the ribosome. Co-translational folding is assumed to guide the folding process into the native structure. The introduced methods enable a classification of protein sequences based on their co-translational folding potential. An extensive, comparative study identifies new characteristics in sequence and structure that are exclusive to co-translationally folding proteins. Furthermore, some hypotheses from literature are disproved that have been proposed based on thought experiments. An extension of the study to real protein structures and domains highlights the alpha/beta-domain proteins. This class shows the strongest bias towards the identified characteristics of co-translational folding proteins.

In the final part of the thesis the focus is shifted to evolutionary studies. Therein, intensive analyses of neutral networks are done that are graph-based tools to study neutral evolution. Neutral networks describe the possible evolutionary pathways that preserve a given function and thus the associated structure. A new sequence design approach is introduced that enables the neutral network exploration without a full sequence space enumeration. This is the first method that is able to design non-degenerated sequences for a given structure, which is known to be a difficult, NP-complete problem. A thorough analysis of the resulting neutral networks in three-dimensional lattice models reveals considerable differences, e.g. in network sizes, compared to two-dimensional models. To focus the investigation of neutral evolution on the structural core of proteins an according H-fold definition is presented. The H-folds enable additional evolutionary studies of the flexible loop regions of proteins.

In conclusion, this thesis describes a variety of new and efficient methods that enable extensive studies of structures and sequences in lattice protein models. All methods are freely available for further research within two software packages and via a web frontend for ad hoc usage. The implemented tools as well as the studies presented thus provide an important contribution to in silico protein research.


Kurzfassung in Deutsch

In fast alle lebenswichtigen Prozesse in lebenden Zellen sind Proteine involviert. Sie wirken hierbei als Regulatoren, Katalysatoren, Transporter und in einer Vielzahl von anderen Funktionen, die durch ihre dreidimensionale Struktur bestimmt werden.

Diese Arbeit befasst sich mit den grundlegenden Zusammenhängen, die der Strukturbildung von Proteinen zugrunde liegen. Dabei ist die Vorhersage ihrer funktionalen Form von zentraler Bedeutung sowie die Modellierung des Faltungsprozesses an sich. Um möglichst umfangreiche Studien zu ermöglichen, werden hierzu Gitterproteinmodelle verwendet, die in einer Vielzahl von Abstraktionsgraden verfügbar sind. Der Fokus der Arbeit liegt auf der Entwicklung und Umsetzung von effizienten Methoden zum Studium von Gitterproteinen in komplexen dreidimensionalen Gittern. Hierbei stehen insbesondere Verfahren im Vordergrund, welche die Verwendung von Seitenkettenmodellen ermöglichen.

Ein wichtiger Schritt ist hierbei der Transfer von realen Proteinstrukturen in das verwendete Modell. Dieses NP-vollständige Problem wird im ersten Teil der Arbeit behandelt. Eine Kombination aus effizienten Heuristiken und constraint-basierter Suche liefert Modelle von sehr hoher Qualität in kurzer Laufzeit.

Der zweite Teil der Arbeit geht auf Methoden zur Bestimmung von energieminimalen Strukturen ein. Auch hier kommt ein constraint-basierter Ansatz zum Einsatz der erstmals die Bestimmung von energieoptimalen Strukturen im HP-Seitenkettenmodell ermöglicht. Daraufhin erfolgt die erste Studie optimaler Konformationen in diesem Modell, wobei eine enorme Degeneriertheit beobachtet wird. Da viele Strukturen mit der verwendeten HP-Energiefunktion nicht unterscheidbar sind, wird eine entsprechende Äquivalenzrelation zur Gruppierung ähnlicher Strukturen eingeführt. Eine Erweiterung des constraint-basierten Ansatzes zur Strukturbestimmung ermöglicht die effiziente und direkte Aufzählung der resultierenden Äquivalenzklassen. HP-optimale Strukturen aus verschiedenen Klassen können zur Initialisierung von lokalen Suchverfahren unter Verwendung von umfassenderen Energiemodellen verwendet werden. Die Überlegenheit eines derartigen Ansatzes gegenüber herkömmlichen Strategien wird demonstriert.

Um lokale Suchverfahren auch in Seitenkettenmodellen zu ermöglichen, ist die Definition und effiziente Umsetzung einer Nachbarschaft von Strukturen notwendig. Eine intervallbasierte lokale Nachbarschaftsrelation sowie ein effizientes Verfahrung zu seiner Aufzählung umfasst der dritte Teil der Arbeit.

Anschließend wird das Phänomen der kotranslationalen Faltung untersucht. Dieses beschreibt den Vorgang der Strukturbildung noch während der Konstruktion eines Proteins am Ribosom. Es wird angenommen, dass hierdurch die Faltung in die funktionelle Konformation begünstigt wird. Die eingeführten Verfahren ermöglichen eine Klassifikation von Proteinsequenzen anhand ihres kotranslationellen Faltungspotentials. Eine umfangreiche vergleichende Studie identifiziert neue Charakteristika in Sequenz und Struktur welche kotranslational faltenden Proteinen zugeordnet werden können. Zudem werden einige Hypothesen aus der Literatur widerlegt, welche großteilig auf Gedankenexperimenten basierten. Eine Ausweitung der Studie auf reelle Proteinstrukturen und -domänen hebt die Gruppe der alpha/beta-Domänproteine hervor, die die stärksten Trends zu den identifizierten kotranslationalen Charakteristika aufweisen.

Im finalen Teil der Arbeit wechselt der Fokus auf evolutionäre Fragestellungen. Hierbei erfolgt eine umfangreiche Studie von neutralen Netzwerken, einem graphenbasiertem Werkzeug um neutrale Evolution zu untersuchen. Neutrale Netzwerke beschreiben hierbei mögliche evolutionäre Pfade welche eine gegebene Funktion und somit Struktur erhalten. Es wird ein Sequenzdesignverfahren eingeführt, um die Generierung von neutralen Netzwerken zu ermöglichen. Dieses Verfahren ist das erste, welches nicht-degenerierte Sequenzen für eine gegebene Struktur designen kann, einem schweren, NP-vollständigen Problem. Eine umfangreiche Analyse der resultierenden neutralen Netzwerke in dreidimensionalen Gittern zeigt deutliche Unterschiede, u.a. in ihrer Größe, zu zweidimensionalen Modellen auf. Um die Untersuchung von neutraler Evolution auf den strukturellen Kern von Proteinen zu fokussieren, wird eine neue Definition von sogenannten H-folds eingeführt. Diese ermöglicht darüber hinaus Studien über die Evolution der flexiblen Teile von Proteinen, welche die höchste Sequenzvariation aufweisen.

Zusammenfassend beschreibt diese Arbeit eine Vielzahl von neuen, effizienten Verfahren, welche umfangreiche Studien von Strukturen und Sequenzen in Gitterproteinmodellen ermöglichen.


SWD-Schlagwörter: Proteinfaltung , Modell , Algorithmus , Constraint-Programmierung
Freie Schlagwörter (deutsch): Gitterprotein , HP-Modell
Freie Schlagwörter (englisch): lattice protein , HP-model
CCS Klassifikation J.3 I.2.1
Institut: Institut für Informatik
Fakultät: Technische Fakultät (bisher: Fak. f. Angew. Wiss.)
DDC-Sachgruppe: Technik
Dokumentart: Dissertation
Erstgutachter: Backofen, Rolf (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 27.06.2011
Erstellungsjahr: 2011
Publikationsdatum: 04.07.2011
Indexliste