Effizienter Algorithmus zum Bearbeiten der Entfernung für kurze Sequenzen

7

Ich habe eine Anwendung, die Milliarden von Levenshtein Abstand zwischen Saitenpaaren berechnen muss. Die Strings sind kurze (70 in der Länge) DNA-Sequenzen, die nur aus 4 Zeichen bestehen. Es kann auch angenommen werden, dass eine der Zeichenfolgen fest ist, dh wir vergleichen eine feste Zeichenfolge mit einer Milliarde anderer Zeichenfolgen.

Ich weiß, dass die dynamische Programmierimplementierung der Levenshtein-Distanz , würde gerne wissen, ob es Raum für Verbesserungen gibt. Ich habe diese beiden Algorithmen gefunden:O(mn)

  • O(n+d2) -Algorithmus, bei dem die Bearbeitungsentfernung von Berghel et al . Ich kann jedoch nicht davon ausgehen, dass klein ist, so dass es möglicherweise keinen Vorteil bringtdd
  • log(n)O(1/ϵ) Näherung in Zeit von Andoni et al . Aber ich habe zwei Bedenken: n1+ϵ
    • Ist dieser Algorithmus auch in der Praxis schnell?
    • Bedeutet dass die berechnete Bearbeitungsentfernung im schlimmsten Fall mal der tatsächlichen ist ? In diesem Fall ist es zu viel.log(n)O(1/ϵ)log(n)O(1/ϵ)

Kennen Sie andere Algorithmen / Ideen / Ansätze, die möglicherweise anwendbar sind?

Ameer Jewdaki
quelle
2
Haben Sie sich Levenshtein-Automaten angesehen?
AdrianN
Muss es genau der Levenshtein-Abstand sein, oder ist ein relativ konsistenter Bearbeitungsabstand gut genug?
Pål GD
Interessieren Sie sich nur für die Bearbeitungsentfernung, wenn die Bearbeitungsentfernung unter einem bestimmten Schwellenwert liegt (z. B. wenn die Bearbeitungsentfernung , ist es Ihnen egal, wie genau die Bearbeitungsentfernung ist; wissen Sie nur, dass sie ausreicht)? >20>20
DW
Ist DNA Levenshtein wirklich ähnlich? 11 gegen 00 ist 2 für Levenshtein, aber 10 gegen 01 ist nur 1. Ich wäre wirklich überrascht, wenn DNA ein Match ist oder nicht, ist alles, was zählt.
Paparazzo
@ PålGD Eine gute Annäherung an die Levenshtein-Distanz könnte auch gut sein.
Ameer Jewdaki

Antworten:

3

Ein Ansatz besteht darin, einen Levenshtein-Automaten für die feste Zeichenfolge zu erstellen (siehe z . B. hier ). Gegeben eine Zeichenfolgex und eine Entfernung Dkönnen Sie einen DFA erstellen, der alle Zeichenfolgen erkennt, die sich in einiger Entfernung befinden D von x. Auf diese Weise können Sie testen, ob sich eine Zeichenfolge in der Nähe befindetx im O(n) Zeit, wo nist die Länge der Zeichenfolge. Ich bin mir nicht sicher, wie viel Platz erforderlich ist, um den DFA zu speichern (sie sind linear inm,n, könnte aber exponentiell sein in D).

Alternativ können Sie einen "Early-Out" -Algorithmus zum Berechnen der Bearbeitungsentfernung verwenden. Sie haben erwähnt, dass Sie nur dann an der Bearbeitungsentfernung interessiert sind, wenn diese unter einem bestimmten Schwellenwert liegtD. Es gibt einen "Early-Out" -Algorithmus zum Berechnen der Bearbeitungsentfernung, deren Laufzeit beträgtO(max(n,m)×D), der den Bearbeitungsabstand berechnet, wenn er oder "zu groß" ausgibt, wenn er . Grundsätzlich verwenden Sie den standardmäßigen dynamischen Programmieralgorithmus für die Bearbeitungsentfernung, berechnen jedoch nur die Elemente der Matrix, die von der Diagonale entfernt sind. In Ihrem Fall könnte dies besser sein oder auch nicht als die anderen Alternativen.D>DD

DW
quelle
-1

Wenn ich Milliarden machen müsste und es nur 4 Zeichen wären, würde ich die Zeichen als
1000
0100
0010
0001 darstellen.
Es ist dann eine 35-Byte-Ganzzahl

Punkt ein bisschen weise andund zähle die Einsen

Nicht perfekt, aber Milliarden sind viel, es sei denn, Sie werfen viel CPU darauf.

Paparazzo
quelle
1
Insgesamt sind es einige Billionen Ferngespräche, aber ich habe Zugriff auf einen Computercluster. Das Problem ist, dass bei zwei Zeichenfolgen mit einer Länge von 100 und mehreren Einfügungen oder Löschungen das Punktprodukt von der tatsächlichen Entfernung abweicht.
Ameer Jewdaki
OK, du hast 70 in Länge gesagt. Ich bin überrascht, dass ein auf Wörtern basierender Algorithmus für DNA gilt. Das sind wissenschaftliche DNA-Matching-Gleichungen - ich bin überrascht, dass Sie keine davon verwenden.
Paparazzo
Ich beschwere mich nicht, aber ein DV hilft mir nicht, hier einen besseren Beitrag zu leisten.
Paparazzo
Ich habe die Antwort nicht abgelehnt. Tatsächlich denke ich, dass es im Allgemeinen ein guter Ansatz ist, aber hier ist es wegen Einfügungen / Löschungen zu weit weg.
Ameer Jewdaki
und ja, es gibt probabilistische Möglichkeiten, die Entfernung zwischen zwei DNA-Sequenzen zu definieren, aber keine ist meiner Meinung nach einfacher zu berechnen als die Entfernung zu bearbeiten. Also hier fange ich gerade mit der "einfachen" Maßnahme an
Ameer Jewdaki