Mehrfache Sequenzausrichtung (Längste gemeinsame Subsequenz)? diese

OK ist, was ich tun möchte:Mehrfache Sequenzausrichtung (Längste gemeinsame Subsequenz)? diese

Mehr als zwei Strings und „align“ sie (keine DNA/RNA-Sequenz oder dergleichen, ganz normale Saiten nicht wie 1000 Elemente in jeder von ihnen)

Ich habe bereits einige Arbeiten mit der paarweisen Ausrichtung (zwei Strings) durchgeführt, aber die "Lücken" verursachen einige Probleme, wenn ich versuche, mehr als ein Paar auszurichten.

Beispiel (ein Ich teste derzeit):

ABCDEF 
ABGHCEEF 
AJKLBCDYEOF 

AB--CDEF 
ABGHCEEF 
======================= 
AB--C-EF 

A-B--C--E-F 
AJKLBCDYEOF 
======================= 
A----C--E-F

Und ein anderes (anschauliches) Beispiel:

http://nest.drkameleon.com 
http://www.google.com 
http://www.yahoo.com 

http://nest.drkameleon.com 
http://-www.--google--.com 

======================= 
http://----.------le--.com 

http://----.------le--.com 
http://-www.-----yahoo.com 

======================= 
http://----.----------.com

Was ich zur Zeit mache:

sortiert die Saiten (längere Strings zuerst in der Liste kommen)
das erste Paar ausrichten: AB und das Ergebnis erhalten (sie R1 sagt)
dann das zweite Paar ausrichten: R1 und C (Ergebnis in R2)
dann das dritte Paar ausrichten: R2 und D
und so weiter ...

also, was in Ihrem Verstand? Wie könnte ich dafür gehen? Gibt es einen besseren Weg? (Natürlich muss es sein ...)

Ich würde das lieber in Perl/Python oder etwas in dieser Richtung tun, aber jede Art von Code/Referenz wäre mehr als willkommen! :-)

Quelle

2012-04-09 Dr.Kameleon

Können Sie vielleicht einige Beispiele dafür nennen, was die Ein- und Ausgänge sein könnten? Ich bin nicht 100% auf was du eigentlich willst. –

werfen Sie auch einen Blick auf diesen Artikel, der das LCS-Problem in Python detailliert erklärt. http://wordaligned.org/articles/longest-common-subsequence#toc21 – luke14free

@ Li-aungYip Hier ist, was ich meine: http://StackOverflow.com/Questions/10065293/How-To-align-2-strings –

Ich glaube, Sie in der Lage sein, kann dieses Problem als eine allgemeinere Zeichenfolge diff Problem anstelle einer Zeichenfolge Ausrichtung zu werfen. Überlegen Sie, wie GNU diff verwendet wird, um Unterschiede zwischen zwei Dateien zu finden, und verwenden Sie die gleichen Algorithmen wie für die Ausführung eines N-Wegs diff.

Ich bin mir nicht sicher, ob die Zeit/Speicher-Komplexität dieses Ansatzes für Ihre Bedürfnisse geeignet ist, aber Sie können zumindest über das Problem auf diese Weise nachdenken.

Quelle

2012-04-09 13:18:19

Ich bin mir nicht ganz sicher, wie 'diff' in diesem Fall helfen könnte ... –

Es gibt einen Algorithmus, der auf dem Levenshtein-Algorithmus basiert, um die längste gemeinsame Sequenz mit optionalen Leerzeichen zu berechnen. Nicht sicher, ob das hilft.

Quelle

2012-04-09 15:46:38 Alberto

Nun, offensichtlich habe ich viel mit dem Levenshtein-Algorithmus gespielt, und dann habe ich es sogar mit Hirschbergs versucht, aber was kommt mir vielleicht näher Fall ist der ** Needleman-Wunsch Algorithmus ** (http://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithmus) –

Mehrfache Sequenzausrichtung (Längste gemeinsame Subsequenz)? diese

Antwort

Verwandte Themen