In bioinformatics ist eine Folge-Anordnung eine Weise, die Folgen der DNA, der RNS oder des Proteins einzuordnen, um Gebiete der Ähnlichkeit zu identifizieren, die eine Folge von funktionellen, strukturellen oder evolutionären Beziehungen zwischen den Folgen sein kann. Ausgerichtete Folgen von nucleotide oder Aminosäure-Rückständen werden normalerweise als Reihen innerhalb einer Matrix vertreten. Lücken werden zwischen den Rückständen eingefügt, so dass identische oder ähnliche Charaktere in aufeinander folgenden Säulen ausgerichtet werden.

Schlüssel: Einzelne Briefe: Aminosäuren. Rot: klein, hydrophob, aromatisch, nicht Y. Blau: acidic. Purpurrot: grundlegend. Grün: hydroxyl, Amin, amide, grundlegend. Grau: andere. "*": identisch. ":": erhaltene Ersetzungen (dieselbe Farbengruppe) ".": halberhaltener Ersatz (ähnliche Gestalten).]]

Folge-Anordnungen werden auch für nichtbiologische Folgen verwendet, wie diejenigen präsentieren auf natürlicher Sprache oder in Finanzdaten.

Interpretation

Wenn zwei Folgen in einer Anordnung einen gemeinsamen Ahnen teilen, können Fehlanpassungen als Punkt-Veränderungen und Lücken als indels (d. h. Einfügung oder Auswischen-Veränderungen) eingeführt in einer oder beiden Abstammungen in der Zeit interpretiert werden, seitdem sie von einander abgewichen sind. In Folge-Anordnungen von Proteinen kann der Grad der Ähnlichkeit zwischen Aminosäuren, die eine besondere Position in der Folge besetzen, als ein raues Maß dessen interpretiert werden, wie erhalten besonderes Gebiet- oder Folge-Motiv unter Abstammungen ist. Die Abwesenheit von Ersetzungen oder die Anwesenheit nur sehr konservativer Ersetzungen (d. h. der Ersatz von Aminosäuren, deren Seitenketten ähnliche biochemische Eigenschaften haben) in einem besonderen Gebiet der Folge, weisen darauf hin, dass dieses Gebiet strukturelle oder funktionelle Wichtigkeit hat. Obwohl DNA und RNS nucleotide Basen einander ähnlicher sind, als Aminosäuren sind, kann die Bewahrung von Grundpaaren eine ähnliche funktionelle oder strukturelle Rolle anzeigen.

Anordnungsmethoden

Sehr kurze oder sehr ähnliche Folgen können mit der Hand ausgerichtet werden. Jedoch verlangen interessanteste Probleme die Anordnung von langen, hoch variablen oder äußerst zahlreichen Folgen, die allein durch die menschliche Anstrengung nicht ausgerichtet werden können. Statt dessen werden menschliche Kenntnisse im Konstruieren von Algorithmen angewandt, um Qualitätsfolge-Anordnungen, und gelegentlich in der Anpassung der Endresultate zu erzeugen, Muster zu widerspiegeln, die schwierig sind, algorithmisch (besonders im Fall von nucleotide Folgen) zu vertreten. Rechenbetonte Annäherungen an die Folge-Anordnung fallen allgemein in zwei Kategorien: globale Anordnungen und lokale Anordnungen. Das Rechnen einer globalen Anordnung ist eine Form der globalen Optimierung, die die Anordnung "zwingt", die komplette Länge aller Anfragenfolgen abzumessen. Im Vergleich identifizieren lokale Anordnungen Gebiete der Ähnlichkeit innerhalb von langen Folgen, die häufig insgesamt weit auseinander gehend sind. Lokale Anordnungen sind häufig vorzuziehend, aber können schwieriger sein, wegen der zusätzlichen Herausforderung zu rechnen, die Gebiete der Ähnlichkeit zu identifizieren. Eine Vielfalt von rechenbetonten Algorithmen ist auf das Folge-Anordnungsproblem, einschließlich langsamer, aber formell richtiger Methoden wie dynamische Programmierung, und effizienter, heuristischer Algorithmen oder probabilistic Methoden angewandt worden, die nicht versichern, beste Matchs entworfen für die groß angelegte Datenbanksuche zu finden.

Darstellungen

Anordnungen werden sowohl grafisch als auch im Textformat allgemein vertreten. In fast allen Folge-Anordnungsdarstellungen werden Folgen in eingeordneten Reihen geschrieben, so dass ausgerichtete Rückstände in aufeinander folgenden Säulen erscheinen. In Textformaten werden ausgerichtete Säulen, die identische oder ähnliche Charaktere enthalten, mit einem System von Bewahrungssymbolen angezeigt. Als im Image oben, ein Sternchen oder Pfeife-Symbol wird verwendet, um Identität zwischen zwei Säulen zu zeigen; andere weniger allgemeine Symbole schließen einen Doppelpunkt für konservative Ersetzungen und eine Periode für halbkonservative Ersetzungen ein. Viele Folge-Vergegenwärtigungsprogramme verwenden auch Farbe, um Information über die Eigenschaften der individuellen Folge-Elemente zu zeigen; in der DNA und den RNS-Folgen gleicht das zum Zuweisen jedes nucleotide seine eigene Farbe aus. In Protein-Anordnungen, wie diejenige im Image oben, wird Farbe häufig verwendet, um Aminosäure-Eigenschaften anzuzeigen, im Beurteilen der Bewahrung eines gegebenen Aminosäure-Ersatzes zu helfen. Für vielfache Folgen ist die letzte Reihe in jeder Säule häufig die durch die Anordnung bestimmte Einigkeitsfolge; die Einigkeitsfolge wird auch häufig im grafischen Format mit einem Folge-Firmenzeichen vertreten, in dem die Größe jedes nucleotide oder Aminosäure-Briefs seinem Grad der Bewahrung entspricht.

Folge-Anordnungen können in einem großen Angebot an textbasierten Dateiformaten versorgt werden, von denen viele in Verbindung mit einem spezifischen Anordnungsprogramm oder Durchführung ursprünglich entwickelt wurden. Die meisten webbasierten Werkzeuge erlauben eine begrenzte Zahl des Eingangs und der Produktionsformate, wie FASTA-Format und Format von GenBank, und die Produktion ist nicht leicht editable. Mehrere Umwandlungsprogramme, sind READSEQ verfügbar oder PRÄGEN grafische Schnittstellen oder Befehl-Linienschnittstellen zu haben, während mehrere Programmierpakete wie BioPerl, BioRuby Funktionen zur Verfügung stellen, das zu tun.

Globale und lokale Anordnungen

Globale Anordnungen, die versuchen, jeden Rückstand in jeder Folge auszurichten, sind am nützlichsten, wenn die Folgen im Anfragensatz ähnlich sind und grob der gleichen Größe. (Das bedeutet nicht, dass globale Anordnungen in Lücken nicht enden können.) Ist eine allgemeine globale Anordnungstechnik der Needleman-Wunsch Algorithmus, der auf der dynamischen Programmierung basiert. Lokale Anordnungen sind für unterschiedliche Folgen nützlicher, die, wie man verdächtigt, Gebiete der Ähnlichkeit oder ähnlichen Folge-Motive innerhalb ihres größeren Folge-Zusammenhangs enthalten. Der Algorithmus des Schmieds-Fährmannes ist eine allgemeine lokale auf der dynamischen Programmierung auch gestützte Anordnungsmethode. Mit genug ähnlichen Folgen gibt es keinen Unterschied zwischen lokalen und globalen Anordnungen.

Hybride Methoden, bekannt als halbglobal oder "glocal" (kurz für den global-lokalen) Methoden, versuchen, die bestmögliche Anordnung zu finden, die den Anfang und Ende von einem oder der anderen Folge einschließt. Das kann besonders nützlich sein, wenn der abwärts gelegene Teil einer Folge mit stromaufwärts ein Teil der anderen Folge überlappt. In diesem Fall ist weder globale noch lokale Anordnung völlig passend: Eine globale Anordnung würde versuchen, die Anordnung zu zwingen, sich außer dem Gebiet des Übergreifens auszustrecken, während eine lokale Anordnung das Gebiet des Übergreifens nicht völlig bedecken könnte.

Anordnung von Pairwise

Folge-Anordnungsmethoden von Pairwise werden verwendet, um das beste Zusammenbringen piecewise (lokale) oder globale Anordnungen von zwei Anfragenfolgen zu finden. Anordnungen von Pairwise können nur zwischen zwei Folgen auf einmal verwendet werden, aber sie sind effizient, um zu rechnen, und werden häufig für Methoden verwendet, die äußerste Präzision (wie Suche einer Datenbank für Folgen mit der hohen Ähnlichkeit zu einer Abfrage) nicht verlangen. Die drei primären Methoden, pairwise Anordnungen zu erzeugen, sind Punktmatrixmethoden, dynamische Programmierung und Wortmethoden; jedoch können vielfache Folge-Anordnungstechniken auch Paare von Folgen ausrichten. Obwohl jede Methode seine individuellen Kräfte und Schwächen hat, haben alle drei pairwise Methoden Schwierigkeit mit hoch wiederholenden Folgen des niedrigen Informationsinhalts - besonders, wo sich die Zahl von Wiederholungen in den zwei auszurichtenden Folgen unterscheidet. Eine Weise, das Dienstprogramm einer gegebenen pairwise Anordnung zu messen, ist das 'maximale einzigartige Match' (MAMA) oder die längste Subfolge, die in beider Anfragenfolge vorkommt. Längere MAMA-Folgen widerspiegeln normalerweise nähere Zusammenhängendkeit.

Punktmatrixmethoden

Die Punktmatrixannäherung, die implizit eine Familie von Anordnungen für individuelle Folge-Gebiete erzeugt, ist qualitativ und, obwohl zeitraubend, begrifflich einfach, um auf einem in großem Umfang zu analysieren. Ohne Geräusch kann es leicht sein, bestimmte Folge-Eigenschaften — wie Einfügungen, Auswischen, Wiederholungen oder umgekehrte Wiederholungen — von einem Punktmatrixanschlag visuell zu identifizieren. Um einen Punktmatrixanschlag zu bauen, werden die zwei Folgen entlang der Spitzenreihe und leftmost Säule einer zweidimensionalen Matrix geschrieben, und ein Punkt wird an jedem Punkt gelegt, wo die Charaktere im passenden Säulenmatch - das ein typischer Wiederauftreten-Anschlag ist. Einige Durchführungen ändern die Größe oder Intensität des Punkts abhängig vom Grad der Ähnlichkeit der zwei Charaktere, um konservative Ersetzungen anzupassen. Die Punktanschläge sehr nah zusammenhängender Folgen werden als eine einzelne Linie entlang der Hauptdiagonale der Matrix erscheinen.

Probleme mit Punktanschlägen als eine Informationsanzeigetechnik schließen ein: Geräusch, fehlen Sie der Klarheit, Nichtintuitivkeit, Schwierigkeit, die Match-Zusammenfassungsstatistik und Match-Positionen auf den zwei Folgen herauszieht. Es gibt auch viel vergeudeten Raum, wo die Match-Daten über die Diagonale von Natur aus kopiert werden und der grösste Teil des wirklichen Gebiets des Anschlags entweder durch den leeren Raum oder durch das Geräusch, und schließlich aufgenommen wird, werden die Punktanschläge auf zwei Folgen beschränkt. Keine dieser Beschränkungen gilt für Anordnungsdiagramme von Miropeats, aber sie haben ihre eigenen besonderen Fehler.

Punktanschläge können auch verwendet werden, um Wiederholungshäufigkeit mit einer einzelnen Folge zu bewerten. Eine Folge kann gegen sich und Gebiete geplant werden, die sich teilen, werden bedeutende Ähnlichkeiten als Linien von der Hauptdiagonale erscheinen. Diese Wirkung kann vorkommen, wenn ein Protein aus vielfachen ähnlichen Strukturgebieten besteht.

Dynamische Programmierung

Die Technik der dynamischen Programmierung kann angewandt werden, um globale Anordnungen über den Needleman-Wunsch Algorithmus und lokale Anordnungen über den Algorithmus des Schmieds-Fährmannes zu erzeugen. Im typischen Gebrauch verwenden Protein-Anordnungen eine Ersatz-Matrix, um Hunderte Aminosäure-Matchs oder Fehlanpassungen und einer Lücke-Strafe zuzuteilen, für eine Aminosäure in einer Folge zu einer Lücke im anderen zu vergleichen. DNA und RNS-Anordnungen können eine Zählen-Matrix verwenden, aber in der Praxis häufig einfach eine positive Match-Kerbe, eine negative Fehlanpassungskerbe und eine negative Lücke-Strafe zuteilen. (In der dynamischen Standardprogrammierung ist die Kerbe jeder Aminosäure-Position der Identität seiner Nachbarn unabhängig, und deshalb werden Grundstapeln-Effekten nicht in Betracht gezogen. Jedoch ist es möglich, für solche Effekten durch das Ändern des Algorithmus verantwortlich zu sein.)

Eine allgemeine Erweiterung auf geradlinige Standardlücke-Kosten, ist der Gebrauch von zwei verschiedenen Lücke-Strafen, für eine Lücke zu öffnen und für eine Lücke zu erweitern. Normalerweise ist der erstere viel größer als die Letzteren, z.B-10 für die Lücke offen und-2 für die Lücke-Erweiterung.

So wird die Anzahl von Lücken in einer Anordnung gewöhnlich vermindert und Rückstände, und Lücken werden zusammen behalten, der normalerweise mehr biologischen Sinn hat. Der Gotoh Algorithmus führt affine Lücke-Kosten durch das Verwenden von drei matrices durch.

Dynamische Programmierung kann im Übereinstimmen nucleotide zu Protein-Folgen, eine durch das Bedürfnis komplizierte Aufgabe nützlich sein, frameshift Veränderungen (gewöhnlich Einfügungen oder Auswischen) in Betracht zu ziehen. Die framesearch Methode erzeugt eine Reihe von globalen oder lokalen pairwise Anordnungen zwischen einer Abfrage nucleotide Folge und einem Suchsatz von Protein-Folgen, oder umgekehrt. Seine Fähigkeit, durch eine beliebige Zahl von nucleotides ausgeglichenen frameshifts zu bewerten, macht die Methode nützlich für Folgen, die große Anzahl von indels enthalten, der sehr schwierig sein kann, sich auf effizientere heuristische Methoden auszurichten. In der Praxis verlangt die Methode große Beträge der Rechenmacht oder eines Systems, dessen Architektur für die dynamische Programmierung spezialisiert wird. Die DRUCKWELLE und PRÄGT Gefolge stellen grundlegende Werkzeuge zur Verfügung, um übersetzte Anordnungen zu schaffen (obwohl einige dieser Annäherungen Nebenwirkungen von Folge-Suche-Fähigkeiten zu den Werkzeugen ausnutzen). Allgemeinere Methoden sind von beiden kommerziellen Quellen, wie FrameSearch, verteilt als ein Teil des Accelrys GCG Paket und Software des Open Sources wie Genewise verfügbar.

versichert, findet das dynamische Programmierverfahren eine optimale Anordnung gegeben eine besondere zählende Funktion; jedoch ist das Identifizieren einer guten zählenden Funktion häufig ein empirischer aber nicht eine theoretische Sache. Obwohl dynamische Programmierung zu mehr als zwei Folgen ausziehbar ist, ist es für die große Anzahl oder äußerst langen Folgen untersagend langsam.

Wortmethoden

Wortmethoden, auch bekannt als K-Tupel-Methoden, sind heuristische Methoden, die, wie man versichert, keine optimale Anordnungslösung finden, aber bedeutsam effizienter sind als dynamische Programmierung. Diese Methoden sind in groß angelegten Datenbanksuchen besonders nützlich, wo es verstanden wird, dass ein großes Verhältnis der Kandidat-Folgen im Wesentlichen kein bedeutendes Match mit der Anfragenfolge haben wird. Wortmethoden sind für ihre Durchführung in den Datenbanksuchwerkzeugen FASTA und die DRUCKWELLE-Familie am besten bekannt. Wortmethoden identifizieren eine Reihe von kurzen, nichtüberlappenden Subfolgen ("Wörter") in der Anfragenfolge, die dann zu Kandidat-Datenbankfolgen verglichen werden. Die Verhältnispositionen des Wortes in den zwei Folgen, die vergleichen werden, werden abgezogen, um einen Ausgleich zu erhalten; das wird ein Gebiet der Anordnung anzeigen, wenn vielfache verschiedene Wörter denselben Ausgleich erzeugen. Nur wenn dieses Gebiet entdeckt wird, tun diese Methoden wenden empfindlichere Anordnungskriterien an; so werden viele unnötige Vergleiche mit Folgen keiner merklichen Ähnlichkeit beseitigt.

In der FASTA Methode definiert der Benutzer einen Wert k, um als die Wortlänge zu verwenden, mit der man die Datenbank sucht. Die Methode ist langsamer, aber an niedrigeren Werten von k empfindlicher, die auch für Suchen bevorzugt werden, die mit einer sehr kurzen Anfragenfolge verbunden sind. Die DRUCKWELLE-Familie von Suchmethoden stellt mehrere Algorithmen zur Verfügung, die für besondere Typen von Abfragen, wie das Suchen nach entfernt zusammenhängenden Folge-Matchs optimiert sind. DRUCKWELLE wurde entwickelt, um eine schnellere Alternative zu FASTA zur Verfügung zu stellen, ohne viel Genauigkeit zu opfern; wie FASTA verwendet DRUCKWELLE eine Wortsuche der Länge k, aber bewertet nur die bedeutendsten Wortmatchs, aber nicht jedes Wortmatch, wie FASTA tut. Die meisten DRUCKWELLE-Durchführungen verwenden eine feste Verzug-Wortlänge, die für die Abfrage und den Datenbanktyp optimiert wird, und das nur unter speziellen Verhältnissen, solcher als geändert wird, wenn man mit wiederholenden oder sehr kurzen Anfragenfolgen sucht. Durchführungen können über mehreres Webportal, wie EMBL FASTA und NCBI-DRUCKWELLE gefunden werden.

Vielfache Folge-Anordnung

Vielfache Folge-Anordnung ist eine Erweiterung der pairwise Anordnung, um mehr als zwei Folgen auf einmal zu vereinigen. Vielfache Anordnungsmethoden versuchen, alle Folgen in einem gegebenen Anfragensatz auszurichten. Vielfache Anordnungen werden häufig im Identifizieren von erhaltenen Folge-Gebieten über eine Gruppe von Folgen verwendet, die Hypothese aufgestellt sind, evolutionär verbunden zu sein. Solche erhaltenen Folge-Motive können in Verbindung mit der strukturellen und mechanistischen Information verwendet werden, um die katalytischen aktiven Seiten von Enzymen ausfindig zu machen. Anordnungen werden auch verwendet, um im Herstellen von Entwicklungsbeziehungen durch das Konstruieren phylogenetic von Bäumen zu helfen. Vielfache Folge-Anordnungen sind rechenbetont schwierig zu erzeugen, und die meisten Formulierungen des Problems führen zu NP-complete kombinatorischen Optimierungsproblemen. Dennoch hat das Dienstprogramm dieser Anordnungen in bioinformatics zur Entwicklung einer Vielfalt von Methoden geführt, die passend sind, um drei oder mehr Folgen auszurichten.

Dynamische Programmierung

Die Technik der dynamischen Programmierung ist auf jede Zahl von Folgen theoretisch anwendbar; jedoch, weil es sowohl in der Zeit als auch im Gedächtnis rechenbetont teuer ist, wird es für mehr als drei oder vier Folgen in seiner grundlegendsten Form selten verwendet. Diese Methode verlangt das Konstruieren der n-dimensional Entsprechung von der von zwei Folgen gebildeten Folge-Matrix, wo n die Zahl von Folgen in der Abfrage ist. Dynamische Standardprogrammierung wird zuerst auf allen Paaren von Anfragenfolgen verwendet, und dann wird der "Anordnungsraum" durch das Betrachten möglicher Matchs oder Lücken an Zwischenpositionen, schließlich das Konstruieren einer Anordnung im Wesentlichen zwischen jeder Zwei-Folgen-Anordnung ausgefüllt. Obwohl diese Technik rechenbetont teuer ist, ist seine Garantie einer globalen optimalen Lösung in Fällen nützlich, wo nur einige Folgen genau ausgerichtet werden müssen. Eine Methode, für die rechenbetonten Anforderungen der dynamischen Programmierung zu reduzieren, die sich auf die "Summe von Paaren" objektive Funktion verlässt, ist im MSA Softwarepaket durchgeführt worden.

Progressive Methoden

Progressiv, hierarchisch, oder Baummethoden erzeugen eine vielfache Folge-Anordnung durch das erste Übereinstimmen der ähnlichsten Folgen und dann Hinzufügen nacheinander weniger zusammenhängender Folgen oder Gruppen zur Anordnung, bis der komplette Anfragensatz in die Lösung vereinigt worden ist. Der anfängliche Baum, der die Folge-Zusammenhängendkeit beschreibt, basiert auf pairwise Vergleichen, die heuristische pairwise FASTA ähnliche Anordnungsmethoden einschließen können. Progressive Anordnungsergebnisse sind von der Wahl "am meisten zusammenhängender" Folgen abhängig und können so zu Ungenauigkeiten in der Initiale pairwise Anordnungen empfindlich sein. Die meisten progressiven vielfachen Folge-Anordnungsmethoden beschweren zusätzlich die Folgen im Anfragensatz gemäß ihrer Zusammenhängendkeit, die die Wahrscheinlichkeit reduziert, eine schlechte Wahl von anfänglichen Folgen zu machen, und so Anordnungsgenauigkeit verbessert.

Viele Schwankungen von Clustal progressive Durchführung werden für die vielfache Folge-Anordnung, phylogenetic Baumaufbau, und wie eingegeben, für die Protein-Struktur-Vorhersage verwendet. Eine langsamere, aber genauere Variante der progressiven Methode ist als T-Kaffee bekannt.

Wiederholende Methoden

Wiederholende Methoden versuchen, die schwere Abhängigkeit von der Genauigkeit der Initiale pairwise Anordnungen zu übertreffen, der der schwache Punkt der progressiven Methoden ist. Wiederholende Methoden optimieren eine objektive auf einer ausgewählten Anordnungszählen-Methode gestützte Funktion durch das Zuweisen einer anfänglichen globalen Anordnung und dann das Wiederübereinstimmen von Folge-Teilmengen. Die wiederausgerichteten Teilmengen werden dann selbst ausgerichtet, um die vielfache Folge-Anordnung der folgenden Wiederholung zu erzeugen. Verschiedene Weisen, die Folge-Untergruppen und objektive Funktion auszuwählen, werden darin nachgeprüft.

Motiv-Entdeckung

Motiv-Entdeckung, auch bekannt als Profil-Analyse, bauen globale vielfache Folge-Anordnungen, die versuchen, kurze erhaltene Folge-Motive unter den Folgen im Anfragensatz auszurichten. Das wird gewöhnlich durch das erste Konstruieren einer allgemeinen globalen vielfachen Folge-Anordnung getan, nach der die hoch erhaltenen Gebiete isoliert und verwendet werden, um eine Reihe des Profils matrices zu bauen. Die Profil-Matrix für jedes erhaltene Gebiet wird wie eine Zählen-Matrix eingeordnet, aber seine Frequenzzählen für jede Aminosäure oder nucleotide an jeder Position werden aus dem Charakter-Vertrieb des erhaltenen Gebiets aber nicht von einem allgemeineren empirischen Vertrieb abgeleitet. Das Profil matrices wird dann verwendet, um andere Folgen für Ereignisse des Motivs zu suchen, das sie charakterisieren. In Fällen, wo die ursprüngliche Datei eine kleine Zahl von Folgen enthalten hat, oder nur hoch Folgen verbunden hat, werden Pseudozählungen hinzugefügt, um den im Motiv vertretenen Charakter-Vertrieb zu normalisieren.

Techniken durch die Informatik begeistert

Eine Vielfalt von allgemeinen in der Informatik allgemein verwendeten Optimierungsalgorithmen ist auch auf das vielfache Folge-Anordnungsproblem angewandt worden. Verborgene Modelle von Markov sind verwendet worden, um Wahrscheinlichkeitshunderte für eine Familie von möglichen vielfachen Folge-Anordnungen für einen gegebenen Anfragensatz zu erzeugen; obwohl früh HMM-basierte Methoden underwhelming Leistung erzeugt haben, haben spätere Anwendungen sie besonders wirksam im Ermitteln entfernt zusammenhängender Folgen gefunden, weil sie gegen das durch konservative oder halbkonservative Ersetzungen geschaffene Geräusch weniger empfindlich sind. Genetische Algorithmen und das vorgetäuschte Ausglühen sind auch in der Optimierung vielfacher Folge-Anordnungshunderte, wie beurteilt, durch eine Zählen-Funktion wie die Methode der Summe Paare verwendet worden. Mehr ganze Details und Softwarepakete können im Hauptartikel vielfache Folge-Anordnung gefunden werden.

Strukturanordnung

Strukturanordnungen, die gewöhnlich zum Protein und manchmal den RNS-Folgen spezifisch sind, verwenden Information über die sekundäre und tertiäre Struktur des Proteins oder RNS-Moleküls, um im Übereinstimmen der Folgen zu helfen. Diese Methoden können für zwei oder mehr Folgen verwendet werden und normalerweise lokale Anordnungen erzeugen; jedoch, weil sie von der Verfügbarkeit der Strukturinformation abhängen, können sie nur für Folgen verwendet werden, deren entsprechende Strukturen (gewöhnlich durch die Röntgenstrahl-Kristallographie oder NMR Spektroskopie) bekannt sind. Weil sowohl Protein-als auch RNS-Struktur evolutionärer erhalten wird als Folge, können Strukturanordnungen zwischen Folgen zuverlässiger sein, die sehr entfernt verbunden sind, und die so umfassend abgewichen sind, dass Folge-Vergleich ihre Ähnlichkeit nicht zuverlässig entdecken kann.

Strukturanordnungen werden als die "Goldwährung" im Auswerten von Anordnungen für die Homologie-basierte Protein-Struktur-Vorhersage verwendet, weil sie ausführlich Gebiete der Protein-Folge ausrichten, die strukturell ähnlich sind, anstatt sich exklusiv auf die Folge-Information zu verlassen. Jedoch können klar strukturelle Anordnungen nicht in der Struktur-Vorhersage verwendet werden, weil mindestens eine Folge im Anfragensatz das zu modellierende Ziel ist, für den die Struktur nicht bekannt ist. Es ist gezeigt worden, dass, in Anbetracht der Strukturanordnung zwischen einem Ziel und einer Schablone-Folge, hoch genaue Modelle der Zielprotein-Folge erzeugt werden können; ein Hauptstolperstein in der Homologie-basierten Struktur-Vorhersage ist die Produktion strukturell genauer Anordnungen gegeben nur Folge-Information.

DALI

Die Methode von DALI oder Entfernungsmatrixanordnung, ist eine Bruchstück-basierte Methode, um Strukturanordnungen zu bauen, die auf Kontakt-Ähnlichkeitsmustern zwischen aufeinander folgendem hexapeptides in den Anfragenfolgen gestützt sind. Es kann pairwise oder vielfache Anordnungen erzeugen und eine Abfrage die Strukturnachbarn der Folge in Protein Data Bank (PDB) identifizieren. Es ist verwendet worden, um die FSSP Strukturanordnungsdatenbank (Falte-Klassifikation zu bauen, die auf der Anordnung der Struktur-Struktur von Proteinen oder Familien Strukturell Ähnlicher Proteine gestützt ist). Auf einen DALI webserver kann an EBI DALI zugegriffen werden, und der FSSP wird an Der Datenbank von Dali gelegen.

SSAP

SSAP (folgendes Struktur-Anordnungsprogramm) ist eine dynamische programmierbasierte Methode der Strukturanordnung, die Atom-zu-Atom-Vektoren im Struktur-Raum verwendet, weil Vergleich hinweist. Es ist seit seiner ursprünglichen Beschreibung erweitert worden, um vielfache sowie pairwise Anordnungen einzuschließen, und ist im Aufbau des CATH (Klasse, Architektur, Topologie, Homologie) hierarchische Datenbankklassifikation von Protein-Falten verwendet worden. Auf die CATH Datenbank kann an der CATH Protein-Struktur-Klassifikation zugegriffen werden.

Kombinatorische Erweiterung

Die kombinatorische Erweiterungsmethode der Strukturanordnung erzeugt eine pairwise Strukturanordnung durch das Verwenden lokaler Geometrie, um kurze Bruchstücke der zwei Proteine auszurichten, die analysieren werden, und sammelt dann diese Bruchstücke in eine größere Anordnung. Gestützt auf Maßnahmen wie Wurzel des starren Körpers bedeuten Quadratentfernung, Rückstand-Entfernungen, lokale sekundäre Struktur, und Umgebung von Umwelteigenschaften wie Rückstand grenzt an hydrophobicity, lokale Anordnungen genannt "ausgerichtete Bruchstück-Paare" werden erzeugt und verwendet, um eine Ähnlichkeitsmatrix zu bauen, die alle möglichen Strukturanordnungen innerhalb von vorherbestimmten Abkürzungskriterien vertritt. Ein Pfad von einem Protein-Struktur-Staat bis den anderen wird dann durch die Matrix durch das Verlängern der wachsenden Anordnung ein Bruchstück auf einmal verfolgt. Das optimale solcher Pfad definiert die Anordnung der kombinatorischen Erweiterung. Ein webbasierter Server, der die Methode durchführt und eine Datenbank von pairwise Anordnungen von Strukturen in der Protein-Datenbank zur Verfügung stellt, wird an der Kombinatorischen Erweiterungswebsite gelegen.

Analyse von Phylogenetic

Phylogenetics und Folge-Anordnung sind nah verwandte Felder wegen der geteilten Notwendigkeit, Folge-Zusammenhängendkeit zu bewerten. Das Feld von phylogenetics macht umfassenden Gebrauch von Folge-Anordnungen im Aufbau und der Interpretation von phylogenetic Bäumen, die verwendet werden, um die Entwicklungsbeziehungen zwischen homologen in den Genomen der auseinander gehenden Arten vertretenen Genen zu klassifizieren. Der Grad, zu dem sich Folgen in einem Anfragensatz unterscheiden, ist qualitativ mit der Entwicklungsentfernung der Folgen von einander verbunden. Grob sprechend, weist hohe Folge-Identität darauf hin, dass die fraglichen Folgen einen verhältnismäßig jungen neusten gemeinsamen Ahnen haben, während niedrige Identität darauf hinweist, dass die Abschweifung älter ist. Diese Annäherung, die die "molekulare Uhr" Hypothese widerspiegelt, dass eine grob unveränderliche Rate der Entwicklungsänderung verwendet werden kann, um die verbrauchte Zeit zu extrapolieren, seitdem zwei Gene zuerst (d. h. die Fusionszeit) abgewichen sind, nimmt an, dass die Effekten der Veränderung und Auswahl über Folge-Abstammungen unveränderlich sind. Deshalb ist es für möglichen Unterschied unter Organismen oder Arten in den Raten der DNA-Reparatur oder der möglichen funktionellen Bewahrung von spezifischen Gebieten in einer Folge nicht verantwortlich. (Im Fall von nucleotide Folgen rabattiert die molekulare Uhr-Hypothese in seiner grundlegendsten Form auch den Unterschied in Annahmeraten zwischen stillen Veränderungen, die die Bedeutung eines gegebenen codon und anderer Veränderungen nicht verändern, die auf eine verschiedene Aminosäure hinauslaufen, die ins Protein wird vereinigt.) Mehr statistisch genaue Methoden erlauben der Entwicklungsrate auf jedem Zweig des phylogenetic Baums, sich zu ändern, so bessere Schätzungen von Fusionszeiten für Gene erzeugend.

Progressive vielfache Anordnungstechniken erzeugen einen phylogenetic Baum notwendigerweise, weil sie Folgen in die wachsende Anordnung in der Größenordnung von der Zusammenhängendkeit vereinigen. Andere Techniken, die vielfache Folge-Anordnungen und phylogenetic Baumkerbe und Sorte-Bäume zuerst sammeln und eine vielfache Folge-Anordnung vom im höchsten Maße zählenden Baum berechnen. Allgemein verwendete Methoden des phylogenetic Baumaufbaus sind hauptsächlich heuristisch, weil das Problem, den optimalen Baum wie das Problem auszuwählen, die optimale vielfache Folge-Anordnung auszuwählen, NP-hard ist.

Bewertung der Bedeutung

Folge-Anordnungen sind in bioinformatics nützlich, um Folge-Ähnlichkeit zu identifizieren, phylogenetic Bäume erzeugend, und Homologie-Modelle von Protein-Strukturen entwickelnd. Jedoch ist die biologische Relevanz von Folge-Anordnungen nicht immer klar. Wie man häufig annimmt, widerspiegeln Anordnungen, dass ein Grad der Entwicklungsänderung zwischen Folgen von einem gemeinsamen Ahnen hinuntergestiegen ist; jedoch ist es formell möglich, dass konvergente Evolution vorkommen kann, um offenbare Ähnlichkeit zwischen Proteinen zu erzeugen, die evolutionär ohne Beziehung sind, aber ähnliche Funktionen durchführen und ähnliche Strukturen haben.

In Datenbanksuchen wie DRUCKWELLE können statistische Methoden die Wahrscheinlichkeit einer besonderen Anordnung zwischen Folgen oder Folge-Gebieten bestimmen, die zufällig gegeben die Größe und Zusammensetzung der Datenbank entstehen, die wird sucht. Diese Werte können sich bedeutsam abhängig vom Suchraum ändern. Insbesondere die Wahrscheinlichkeit, eine gegebene Anordnung zu finden, nimmt zufällig zu, wenn die Datenbank nur aus Folgen von demselben Organismus wie die Anfragenfolge besteht. Wiederholende Folgen in der Datenbank oder Abfrage können auch sowohl die Suchergebnisse als auch die Bewertung der statistischen Bedeutung verdrehen; SPRENGEN SIE automatisch filtert solche wiederholenden Folgen in der Abfrage, um offenbare Erfolge zu vermeiden, die statistische Kunsterzeugnisse sind.

Methoden der statistischen Bedeutungsbewertung für gapped Folge-Anordnungen sind in der Literatur verfügbar.

Bewertung der Vertrauenswürdigkeit

Statistische Bedeutung zeigt die Wahrscheinlichkeit an, dass eine Anordnung einer gegebenen Qualität zufällig entstehen konnte, aber nicht anzeigt, wie viel höher eine gegebene Anordnung zu alternativen Anordnungen derselben Folgen ist. Maßnahmen der Anordnungsvertrauenswürdigkeit zeigen das Ausmaß an, dem die besten zählenden Anordnungen für ein gegebenes Paar von Folgen wesentlich ähnlich sind. Methoden der Anordnungsvertrauenswürdigkeitsbewertung für gapped Folge-Anordnungen sind in der Literatur verfügbar.

Das Zählen von Funktionen

Die Wahl einer Zählen-Funktion, die biologische oder statistische Beobachtungen über bekannte Folgen widerspiegelt, ist für das Produzieren guter Anordnungen wichtig. Protein-Folgen werden oft mit dem Ersatz matrices ausgerichtet, die die Wahrscheinlichkeiten von gegebenen Ersetzungen des Charakters-zu-Buchstaben widerspiegeln. Eine Reihe von matrices genannt PAM matrices (Punkt Akzeptierte Veränderung matrices, ursprünglich definiert von Margaret Dayhoff und manchmal gekennzeichnet als "Dayhoff matrices") verschlüsselt ausführlich Entwicklungsannäherungen bezüglich der Raten und Wahrscheinlichkeiten von besonderen Aminosäure-Veränderungen. Eine andere allgemeine Reihe, matrices, bekannt als BLOSUM (Block-Ersatz-Matrix) einzukerben, verschlüsselt empirisch abgeleitete Ersatz-Wahrscheinlichkeiten. Varianten von beiden Typen von matrices werden verwendet, um Folgen mit sich unterscheidenden Niveaus der Abschweifung zu entdecken, so Benutzern der DRUCKWELLE oder FASTA erlaubend, Suchen auf näher zusammenhängende Matchs einzuschränken oder sich auszubreiten, um mehr auseinander gehende Folgen zu entdecken. Lücke-Strafen sind für die Einführung einer Lücke - auf dem Entwicklungsmodell, einer Einfügung oder der Auswischen-Veränderung - sowohl in nucleotide als auch in Protein-Folgen verantwortlich, und deshalb sollten die Strafwerte zur erwarteten Rate solcher Veränderungen proportional sein. Die Qualität der Anordnungen erzeugt hängt deshalb von der Qualität der Zählen-Funktion ab.

Es kann sehr nützlich und aufschlussreich sein, um dieselbe Anordnung mehrere Male mit verschiedenen Wahlen zu versuchen, um Matrix und/oder Lücke-Strafwerte einzukerben und die Ergebnisse zu vergleichen. Gebiete, wo die Lösung schwach ist oder nichteinzigartige, können häufig durch das Beobachten identifiziert werden, welche Gebiete der Anordnung zu Schwankungen in Anordnungsrahmen robust sind.

Anderer biologischer Gebrauch

Sequenced RNS, wie ausgedrückte Folge-Anhängsel und lebensgroßer mRNAs, kann zu einem sequenced Genom ausgerichtet werden, um zu finden, wo es Gene gibt und Information über das alternative Verstärken und RNS-Redigieren bekommt. Folge-Anordnung ist auch ein Teil des Genom-Zusammenbaues, wo Folgen ausgerichtet werden, um Übergreifen zu finden, so dass contigs (langes Strecken der Folge) gebildet werden kann. Ein anderer Gebrauch ist SNP Analyse, wo Folgen von verschiedenen Personen ausgerichtet werden, um einzelne basepairs zu finden, die häufig in einer Bevölkerung verschieden sind.

Nichtbiologischer Gebrauch

Die für die biologische Folge-Anordnung verwendeten Methoden haben auch Anwendungen in anderen Feldern am meisten namentlich in der Verarbeitung der natürlichen Sprache und in Sozialwissenschaften gefunden, wo der Needleman-Wunsch Algorithmus das gewöhnlich Optimale Zusammenbringen genannt wird. Techniken, die den Satz von Elementen erzeugen, von denen Wörter in Generationsalgorithmen der natürlichen Sprache ausgewählt werden, haben vielfache Folge-Anordnungstechniken von bioinformatics geliehen, um Sprachversionen computererzeugter mathematischer Beweise zu erzeugen. Im Feld der historischen und vergleichenden Linguistik ist Folge-Anordnung verwendet worden, um die vergleichende Methode teilweise zu automatisieren, durch die Linguisten traditionell Sprachen wieder aufbauen. Geschäft und Marktforschung haben auch vielfache Folge-Anordnungstechniken im Analysieren der Reihe von Käufen mit der Zeit angewandt.

Software

Eine mehr ganze Liste der verfügbaren Software, die durch den Algorithmus und Anordnungstyp kategorisiert ist, ist an der Folge-Anordnungssoftware verfügbar, aber allgemeine für allgemeine Folge-Anordnungsaufgaben verwendete Softwarewerkzeuge schließen ClustalW und T-Kaffee für die Anordnung, und die DRUCKWELLE und den FASTA3x für die Datenbanksuche ein.

Anordnungsalgorithmen und Software können direkt im Vergleich zu einander sein, einen standardisierten Satz der Abrisspunkt-Verweisung vielfache als BAliBASE bekannte Folge-Anordnungen verwendend. Die Datei besteht aus Strukturanordnungen, die als ein Standard betrachtet werden können, gegen den rein Folge-basierte Methoden verglichen werden. Die Verhältnisleistung von vielen allgemeinen Anordnungsmethoden auf oft gestoßenen Anordnungsproblemen ist tabellarisiert worden und hat Ergebnisse veröffentlicht online an BAliBASE ausgewählt. Eine umfassende Liste von Hunderten von BAliBASE für viele (zurzeit 12) verschiedene Anordnungswerkzeuge kann innerhalb des Protein-Arbeitstisch-RIEMENS geschätzt werden.

Siehe auch

• Folge, die abbaut
• DRUCKWELLE