92.195.195.74: /* Das Prinzip */ Grammatik korrigiert

2025-02-17T15:26:42Z

Das Prinzip: Grammatik korrigiert

Neue Seite

{{Belege fehlen|Es gibt zwar Literaturangaben, aber keine Einzelnachweise für besitmmte Aussagen--[[Benutzer:Ilikelifesciences|Ilikelifesciences]] ([[Benutzer Diskussion:Ilikelifesciences|Diskussion]]) 11:03, 23. Mär. 2016 (CET)}}
'''''Sequenzalignment''''' (von lateinisch ''sequentia'', „Aufeinanderfolge“ und englisch ''alignment'', „Abgleich, Anordnung, Ausrichtung“) bezeichnet den [[Methode (Erkenntnistheorie)|methodischen]] Vergleich zweier oder mehrerer [[Nukleotidsequenz|Nukleotid-]] oder [[Aminosäuresequenz]]en in linearer Abfolge. Sequenzalignment ist ein Teilgebiet des [[Pattern Matching]]. Es wird in der [[Molekulare Phylogenie|molekularen Phylogenie]] verwendet, um die funktionelle oder [[evolution]]äre Verwandtschaft ([[Homologie (Genetik)|Homologie]]) von Nukleotidsequenzen oder Aminosäuresequenzen zu untersuchen. In der Fachsprache werden anstelle des Anglizismus ''„alignment“'' auch die eingedeutschten Begriffe ''Alignierung'' oder ''Alinierung'' benutzt.

== Das Prinzip ==
Beim Sequenzalignment ordnet man die linear abfolgenden Elemente eines untersuchten Strings („Zeichenfolge“, von englisch ''string'', „Schnur, Saite“) aus dem Datensatz einer Nukleotid- oder Aminosäuresequenz einem anderen String zu.

Es gibt vor allem automatisierte Sequenzalignmentmethoden für große Datensätze von Nukleotid- oder Aminosäuresequenzen. Man kann kleinere Datensätze jedoch auch manuell alignieren. Die manuelle Methode ermöglicht eine größere Sorgfalt und den Ausschluss von hochvariablen und somit nicht alignierbaren Positionen, die spätere Analysen stören würden.

Beim Sequenzalignment soll die Reihenfolge der linear abfolgenden Elemente erhalten bleiben und jedes Element einem anderen Element oder einem ''[[Gap (Bioinformatik)|Gap]]'' („Leerstelle, Lücke“) in jedem String paarig zugeordnet werden. Fehlpaarungen werden als [[Mutation]]en interpretiert, Gaps hingegen als [[Gendeletion]]en oder [[Insertion (Genetik)|Insertionen]] ([[Indel]]).
Die einander zugeordneten Elemente sollten identisch oder biochemisch möglichst ähnlich sein, weil viele gleiche oder ähnliche Elemente in gleicher Reihenfolge auf eine evolutionäre oder funktionelle Verwandtschaft hinweisen. Die Ähnlichkeit der Elemente wird meist vorgegeben und hängt von den Eigenschaften der verwendeten [[Daten]] oder [[Substitutionsmatrix|Substitutionsmatrizes]] ab. Damit ein sinnvolles Alignment möglich ist und da die untersuchten Sequenzen oft unterschiedlich lang sind, dürfen künstlich Gaps in die Strings eingefügt werden.
[[Datei:Zinc-finger-seq-alignment2.png|gerahmt|zentriert|Ein Sequenzalignment, erstellt mit [[ClustalW]], zwischen zwei [[mensch]]lichen [[Zinkfingerprotein]]en aus der [[GenBank]]]]

Das Alignment von zwei Sequenzen wird als ''paarweises Alignment'' bezeichnet, das von mehreren als ''multiples Alignment''. Beim ''paarweisen Alignment'' unterscheidet man weiterhin zwischen globalem, lokalem und semiglobalem Alignment.

=== Kostenfunktion bei automatisiertem Alignment ===
Die Aufgabe eines Alignment-Algorithmus ist, ein Alignment zu finden, das unter einer Kostenfunktion (''alignment score'') optimal ist. Die Kostenfunktion in der Bioinformatik wird meist in einer so genannten „Ähnlichkeitsmatrix“, auch „Austauschmatrix“, (engl.: ''similarity matrix'' oder ''mutation data matrix'') vorgegeben. Diese geben für jedes Paar zu vergleichender Sequenzelemente an, wie wahrscheinlich es ist, dass diese Paarung durch Evolution entstanden ist. Identische Elemente werden hoch bewertet, „ähnliche“ Elemente weniger hoch, stark unterschiedliche Elemente setzen den ''score'' herab. Die Kostenfunktion hat zur Folge, dass das rechnerisch beste Alignment auch dasjenige ist, das zu erwarten wäre, wenn die beiden Sequenzen [[Homologie (Genetik)|homolog]] sind. Ein Problem stellen dabei Gaps dar; für die Entstehung von Insertionen oder Deletionen in biologischen Sequenzen gibt es bislang keine genauen mathematischen Modelle. Man benutzt deswegen empirisch motivierte, sogenannte ''affine gap scores'', die einen konstanten Beitrag für die Einführung jedes Gaps vom Ergebnis abziehen und einen weiteren Beitrag, der linear mit der Länge des Gaps wächst.

=== Beispiel ===
-AAACGG
AAAACCG

Das oben dargestellte Alignment von zwei kurzen DNA-Sequenzen zeigt an der ersten Position (<code>-A</code>), dass ein Gap eingefügt werden kann, um Längenunterschiede auszugleichen. Das Gap wurde am Anfang der oberen Sequenz eingefügt und nicht in der Mitte, weil es aus der Sicht der [[Biologie]] [[Wahrscheinlichkeit|wahrscheinlicher]] ist, dass eine Sequenz an den Enden [[Mutation|mutiert]] als in der Mitte.

An der vorletzten Stelle wurden C und G aligniert, da in der DNA durchaus Mutationen möglich sind, in denen statt eines C zufällig ein G eingebaut wird, oder umgekehrt. Es wäre auch möglich gewesen, G und C jeweils mit einem Gap in der anderen Sequenz zu alignieren. Diese Entscheidung hängt von der verwendeten Kostenfunktion ab.

Beim Proteinsequenzalignment entsprechen die [[Aminosäure]]sequenzen den Strings. Die Kostenfunktionen für die Ähnlichkeiten der einzelnen Aminosäuren untereinander sind etwas komplexer als bei der DNA.

== Paarweises Alignment ==
Ein Alignment von zwei Symbol-Sequenzen <math>S,T</math> ist eine Sequenz von Edit-Operationen, die eine Transformation von <math>S</math> nach <math>T</math> beschreibt. Dabei kann ein Symbol durch ein anderes Symbol ersetzt (''mismatch''), ein Symbol gelöscht (''deletion'') oder ein Symbol eingefügt werden (''insert''). Üblicherweise werden die an einer Edit-Operation beteiligten Symbole übereinandergeschrieben, wobei das Symbol ''<code>-</code>'' eine durch ein in die andere Sequenz eingefügtes bzw. gelöschtes Symbol entstandene Lücke bezeichnet.

Jeder Edit-Operation kann durch eine [[Optimierungsproblem|Bewertungsfunktion]] ein Wert zugeordnet werden. Die Summe der Werte aller Edit-Operationen eines Alignments wird als Alignment-Score bezeichnet.

Ein optimales Alignment ist ein Alignment, dessen Score unter einem Bewertungsschema optimal ist.

Dabei wird manchmal zwischen den Begriffen Score und Edit-Distanz unterschieden. Der Begriff Score bzw. Distanz wird dann bei einem Schema verwendet, das Sequenz-Ähnlichkeiten bzw. Sequenz-Unterschiede durch positive Werte bewertet. D.h. nach dieser Unterscheidung ist ein optimaler Score bzw. eine optimale Distanz maximal bzw. minimal.

Ein Beispiel für ein Bewertungsschema sind die Einheitskosten (unit costs). Die Bewertungsfunktion <math>\delta</math> ist definiert als:

<math>\delta(a, b) = \begin{Bmatrix}
0 & a = b ~~ \text{match} \\
1 & a \neq b ~~\text{mismatch}
\end{Bmatrix}
</math>

<math>\delta(a,-) = 1 ~~ \text{Deletion}</math>

<math>\delta(-,b) = 1 ~~ \text{Insertion}</math>

=== Globales Alignment ===
Bei einem globalen Alignment zwischen zwei Sequenzen werden alle Symbole berücksichtigt. Globale Alignments werden hauptsächlich verwendet, wenn die zu untersuchenden Sequenzen ähnlich lang sind und starke Sequenzhomologien erwartet werden.

Die Berechnung des optimalen Alignment-Score bzw. des optimalen Alignment ist ein [[Optimierungsproblem]], das beim paarweisen Alignment mit der Methode der [[Dynamische Programmierung|dynamischen Programmierung]] ([[Needleman-Wunsch-Algorithmus]]) effizient (Laufzeit in <math>O(n^2)</math>) gelöst werden kann.

'''Beispiel'''
* Gegeben: Zwei Sequenzen S und T, Einheitskosten als Bewertungsschema
* Annahme: S und T haben gemeinsame Vorfahren (sind homolog).
* Frage: Welche Positionen in S und T sind homolog?
Für S = GAC und T = GC sind mögliche Lösungen:
{| class="wikitable" style="text-align:center"
|- class="hintergrundfarbe6"
! Möglichkeit !! Alignment !! Score
|-
| 1
|
GAC
GC-
| <code>0+1+1=2</code>
|-
| 2
|
GAC--
---GC
| <code>1+1+1+1+1=5</code>
|-
| 3
|
GAC
G-C
| <code>0+1+0=1</code>
|}

=== Free-Shift Alignment ===
Das [[Needleman-Wunsch-Algorithmus#Free-Shift Alignment|Free-Shift Alignment]] (auch als Semiglobales Alignment oder End-Gap Free Alignment bezeichnet) zweier Sequenzen ist eine Variante des globalen Alignments, bei dem eine Folge von Insertionen bzw. Deletionen am Anfang bzw. am Ende des Alignments in der Berechnung des Scores nicht berücksichtigt werden. Die Berechnung des optimalen Free-Shift Alignment kann in bestimmten Anwendungen sinnvoller sein als die Berechnung des optimalen globalen Alignment, wenn beispielsweise eine Sequenz deutlich länger als die andere ist und ein überstehendes Suffix bzw. Präfix keine Relevanz hat.

=== Lokales Alignment ===
Ein lokales Alignment von zwei Sequenzen <math>S,T</math> ist ein globales Alignment von einer Teilsequenz (Substring) von <math>S</math> und einer Teilsequenz von <math>T</math>. D.h. zur Berechnung des optimalen lokalen Alignment zweier Sequenzen müssen die beiden Teilsequenzen gefunden werden, deren optimaler Alignment-Score maximal ist.
Anwendungsbeispiele für die Berechnung von lokalen Alignments sind die Suche nach gleichen [[Sequenzmotiv|Sequenzmotiven]] oder Domänen bei Proteinen.
Der klassische Algorithmus zur Berechnung von optimalen lokalen Alignments ist der [[Smith-Waterman-Algorithmus]].

== Multiples Sequenzalignment ==
Während das optimale Alignment von zwei Sequenzen mit Hilfe eines [[Computer]]s recht schnell (d. h. in polynomieller Zeit) exakt berechnet werden kann ([[Zeitkomplexität|Laufzeit]] [[Landau-Symbole|O]]<math>(nm)</math>, ''n'' und ''m'' sind die Längen der Sequenzen), ist dies beim ''multiplen Sequenzalignment'' (''[[Englische Sprache|engl.]] multiple sequence alignment'') nicht mehr möglich, da die Laufzeit des Algorithmus zur exakten Berechnung des multiplen Alignment mit der Anzahl der Sequenzen exponentiell wächst (<math>O(2^k n^k)</math>, wobei ''k'' die Anzahl der Sequenzen und n die längste der zu vergleichenden Sequenzen ist).

Um jedoch ein biologisch bzw. evolutionär sinnvolles Alignment berechnen zu können, aus dem sich tatsächlich Gemeinsamkeiten und Unterschiede in Sequenz, [[Proteinstruktur|Struktur]] und Funktion ableiten lassen, braucht man viele lange Sequenzen. Deshalb werden [[Heuristik]]en verwendet, beispielsweise sogenannte ''Progressive Strategien'' (auch ''Hierarchische Methoden'' genannt). Hierbei werden zunächst alle optimalen paarweisen Alignments der zu untersuchenden Sequenzen berechnet und daraus durch [[Clusteranalyse]] (zum Beispiel unter Verwendung eines [[Neighbor-Joining-Algorithmus|Neighbour-Joining-Algorithmus]]) ein [[phylogenetischer Baum]] abgeleitet (der sogenannte ''Guide Tree''). Entlang dieses Baumes wird schließlich schrittweise (''progressiv'', nach dem Prinzip eines [[Greedy-Algorithmus]]) ein multiples Alignment bestimmt, wobei durch dieses heuristische Vorgehen die optimale Lösung nicht garantiert ist.

== Alignment-Algorithmen ==
* [[Needleman-Wunsch-Algorithmus]] (globales Alignment)
* [[Hirschberg-Algorithmus]] (globales Alignment auf linearem Speicherplatz)
* [[Smith-Waterman-Algorithmus]] (lokales Alignment)
* [[Gotoh-Algorithmus]] (globales Alignment bei affinen Gapkosten)

Heuristische Algorithmen für paarweises Alignment:
* [[BLAST-Algorithmus|BLAST]]
* [[FASTA-Algorithmus|FASTA]]

Heuristische Algorithmen für multiples Alignment:
* Populäre Fragment-Basierte Methode [[DIALIGN-TX]]
* Hierarchische Methoden (zum Beispiel [[Feng-Doolittle]])
* [[BLAST-Algorithmus|PSI-BLAST]]

== Verwandte Themen ==
Methoden, wie [[Jukes & Cantor]], [[Kimura-2-Parameter]], [[Felsenstein 81]], [[HKY 85]] (Hasegawa, Kushino & Yano 1985) oder [[General time reversible]] (GTR oder REV) korrigieren Distanzdaten von Sequenzalignments.

== Software ==
Häufig genutzte Programme für allgemeine Sequenzalignments sind [[ClustalW]], [[MAFFT]] und [[T-Coffee]] sowie [[BLAST-Algorithmus|BLAST]] für die Datenbanksuche.

'''Online Interface'''<br />
Das Programm [[STRAP (Software)]] integriert fast alle frei verfügbaren Programme zur Berechnung von Sequenzalignments. Diese werden automatisch installiert und sind dann mit einer komfortablen graphischen Benutzeroberfläche aufrufbar. Dadurch erspart sich der Nutzer die individuelle Installation und das
Erlernen der Kommandozeilensyntax der einzelnen Programme. Da das Berechnen großer Alignments viel Zeit in Anspruch nehmen kann, werden Ergebnisse langwieriger Berechnungen im Cache gespeichert. Wenn für mindestens zwei der Proteine auch 3D-Strukturen vorhanden sind, ist die kombinierte Anwendung von Sequenzalignment und 3D-Strukturüberlagerung zu empfehlen.

== Siehe auch ==
* [[Clustal]]
* [[Dotplot]]

== Literatur ==
* Michael S. Waterman: ''Introduction to Computational Biology: Maps, Sequences and Genomes'', 1995 Chapman & Hall, ISBN 0-412-99391-0.
* Dan Gusfield: ''Algorithms on Strings, Trees, and Sequences'', 1997 Cambridge University Press, ISBN 0-521-58519-8.
* Andreas D. Baxevanis & B. F. Francis Ouellette (Hrsg.): ''Bioinformatics : a practical guide to the analysis of genes and proteins'', 2001 Wiley-Interscience, ISBN 0-471-38391-0.
* Andrea Hansen: ''Bioinformatik : Ein Leitfaden für Naturwissenschaftler'', 2004 Birkhaeuser Verlag, ISBN 3-7643-6253-7.
* Roland Fleißner: ''Sequence alignment and phylogenetic inference'', 2004 Logos Berlin, ISBN 3-8325-0588-1.
* Bernhard Haubold, Thomas Wiehe: '' Introduction to Computational Biology. An Evolutionary Approach'', 2006 Birkhaeuser Verlag, ISBN 3-7643-6700-8.

[[Kategorie:Bioinformatik]]

Sequenzalignment - Versionsgeschichte

92.195.195.74: /* Das Prinzip */ Grammatik korrigiert