Wie vergleicht man Implementierungen von Smith-Waterman-Algorithmen?

Angenommen, Sie haben zwei Implementierungen des Smith-Waterman-Algorithmus (mit welcher Heuristik auch immer sie zur Beschleunigung angewendet werden) für den lokalen Sequenzabgleich genomischer Sequenzen.

Ich würde gerne wissen, ob man sicher sein kann, dass diese Implementierungen gute Arbeit beim Ausrichten leisten (dh das Programm wurde korrekt geschrieben). Wie bewerte ich das?

Ist das eine Frage zur DNA? Könntest du der Frage etwas mehr Kontext geben? Eine bessere Kennzeichnung kann ebenfalls hilfreich sein.
Sie wenden keine Heuristik an, um es zu beschleunigen. Das wesentliche Merkmal des dynamischen Programmieralgorithmus ist, dass er Ihnen eine der richtigen Antworten gibt. Sie müssen es nicht beschleunigen, da es in Echtzeit läuft. Dies ist ein wichtiger Punkt, und ich schlage vor, Sie ändern Ihre Frage.
Ich bin mir nicht sicher, ob „ie“ das richtige Wort ist. Die Ausrichtungsqualität ist eine Frage von Substitutionsmatrizen und Lückenstrafen und hat nichts mit Korrektheit zu tun.
Sie müssen die Frage klären. Smith-Watermann ist ein spezifischer Algorithmus. Es gibt keine anderen Implementierungen davon. Es kann zusätzliche Schritte geben, die in Verbindung mit SW verwendet werden, und wenn Sie nicht zumindest die Namen dieser Pakete angeben, können wir nicht kommentieren, inwiefern eines von ihnen besser als das andere sein könnte. Was den Vergleich angeht, ist die bessere Implementierung diejenige, die Ihre Arbeit in kürzerer Zeit angemessen gut erledigt. Um zu überprüfen, ob das Programm korrekt geschrieben wurde, sollten Sie sich den Quellcode ansehen. Das ist im Wesentlichen Fehlersuche.

Antworten (2)

Es gibt nur zwei Möglichkeiten für die Smith-Waterman-Angleichung an eine gegebene Kostenmatrix. Es ist entweder richtig oder nicht.

Ehrlich gesagt, was auch immer Sie verwenden, es ist wirklich sehr unwahrscheinlich, dass eine reine Smith-Waterman-Implementierung falsch ist. Es ist nicht so kompliziert, wirklich. Es gibt viele heuristische Verbesserungen an Smith-Waterman, aber wenn Sie beide a) sicher sind, dass Sie sie nicht testen möchten b) sicher sind, dass sie nicht verwendet werden, können Sie immer viele zufällige Sequenzen generieren und sie ausrichten in Paaren. Wenn ein Paar nicht auf die gleiche Weise mit der gleichen Punktzahl übereinstimmt, stimmt etwas nicht und Sie sollten weiter nachforschen.

Ich kann mir vorstellen, dass Ihre Frage technisch nur auf einem Informatik-Stack Exchange beantwortet werden kann. Die pragmatische Antwort der Biologie ist, dass es kein Problem gibt. Dies ist ein so gut etablierter Algorithmus, dass die Implementierung auf jeder seriösen Website oder von jedem seriösen Anbieter wahrscheinlich in Ordnung ist. Es ist keine Heuristik beteiligt. Wenn Sie also verschiedene Implementierungen vergleichen, sollten Sie ähnliche Antworten erhalten. Ich sage eher ähnlich als identisch, weil es mehr als eine Ausrichtung mit derselben Punktzahl geben kann, aber nur eine ausgewählt wird. Generell macht es keinen Unterschied.

Ich nehme an, es gibt einen Aspekt des Smith-Waterman-Algorithmus, der sich zwischen den Implementierungen unterscheiden kann, aber es ist einer, für den Sie als Benutzer die letzte Verantwortung tragen – das Bewertungssystem. Ihre Grundannahme ist, dass zwei Sequenzen verwandt sind, und Sie bitten das Programm, Ihnen die paarweise Ausrichtung zu geben, die diese Verwandtschaft „am besten“ ausdrückt. „Best“ im Programm bedeutet die höchste Punktzahl auf einem System, das der Ausrichtung verschiedener Paare aller 20 Aminosäuren (eine Vergleichsmatrix für Proteine) einen anderen Wert zuweist und spezifische Strafen für die Einführung einer Lücke (um eine Einfügung oder Löschung) und die Erweiterung einer einmal eingeführten Lücke.

Welche Möglichkeiten haben Sie und wann kann es notwendig sein, diese auszuüben? Sie können aus verschiedenen Vergleichsmatrizen wählen, die aus der Ausrichtung von Sequenzblöcken für dasselbe Protein in Organismen unterschiedlicher evolutionärer Trennung abgeleitet wurden. Diese Matrizen unterscheiden sich, da einige Aminosäureänderungen nur eine einzige Basenänderung im Codon erfordern, während andere Änderungen an allen drei Positionen eines Codons erfordern. Letztere treten weniger wahrscheinlich über kurze evolutionäre Zeitspannen (z. B. zwischen Maus und Ratte) als über längere (z. B. zwischen Maus und Bakterium) auf. Idealerweise sollten Sie also die Vergleichsmatrix verwenden, die für die zu vergleichenden Sequenzen am besten geeignet ist.

Umstände, in denen Sie vielleicht die Lückenstrafen ändern oder sogar die Vergleichstabellen anpassen möchten, sind zugegebenermaßen esoterisch, aber ich würde raten, dass es besser ist, über die Anwendbarkeit des Bewertungssystems auf Ihr biologisches Problem nachzudenken, als sich Sorgen zu machen, dass jemand dies tun könnte einen Hash der Implementierung des Computeralgorithmus erstellt.

Wie vergleicht man Implementierungen von Smith-Waterman-Algorithmen?
AntwortenHierDatenschutz-Bestimmungen1y, 0v