Ich suche nach einem schnellen Algorithmus für Suchzwecke in einer riesigen Folge (es ist eine Organismusgenomsequenz, die aus Hunderten von Millionen bis Milliarden von Zeichen besteht).
In dieser Zeichenfolge sind nur 4 Zeichen {A, C, G, T} vorhanden, und "A" kann nur mit "T" paaren, während "C" mit "G" gepaart ist.
Jetzt suche ich nach zwei Teilstrings (mit Längenbeschränkung von beiden Teilstrings zwischen {minLen, maxLen} und Intervalllängen zwischen {intervalMinLen, intervalMaxLen}), die sich antiparallel paaren können.
Zum Beispiel Die Zeichenfolge lautet: ATCAG GACCA TACGC CTGAT
Einschränkungen: minLen = 4, maxLen = 5, intervalMinLen = 9, intervalMaxLen = 10
Das Ergebnis sollte
sein"ATCAG" -Paar mit "CTGAT"
"TCAG" -Paar mit "CTGA"
Vielen Dank im Voraus.
Update: Ich habe bereits die Methode, um zu bestimmen, ob zwei Saiten miteinander paaren können. Die einzige Sorge ist erschöpfende Suche ist sehr zeitaufwendig.
Ich dachte, das wäre ein interessantes Problem, deshalb habe ich ein Programm zusammengestellt, das auf "Faltungen" basiert, die nach möglichen symmetrischen Übereinstimmungen von verschiedenen "Faltstellen" suchen. Wenn N die Anzahl der Nukleotide ist und M 'maxInterval-minInterval' ist, sollte die Laufzeit O (N * M) sein. Ich habe vielleicht einige Grenzfälle übersehen, also benutze den Code vorsichtig, aber es funktioniert für das Beispiel, das zur Verfügung gestellt wird. Beachten Sie, dass ich einen gepolsterten Zwischenpuffer verwendet habe, um das Genom zu speichern, da dies die Anzahl der Vergleiche für Grenzfälle, die in den inneren Schleifen benötigt werden, reduziert; Dies kompensiert zusätzliche Speicherzuweisung für eine bessere Geschwindigkeit. Fühlen Sie sich frei, den Beitrag zu bearbeiten, wenn Sie Korrekturen oder Verbesserungen vornehmen.
%Vor%Ich weiß, dass Sie nicht nach Substrings suchen, aber ich denke, es könnte sich lohnen, eine umgekehrte Genom-Zeichenfolge zu erstellen, die die Treffer enthält. Die Aufgabe wäre dann, in den beiden Strings gemeinsame Teilstrings zu finden.
Beispiel:
Ursprüngliche Zeichenfolge
%Vor%Umgekehrte Zeichenfolge:
%Vor%Wenn Sie dann die Zeichenfolge in ihre Paarungswerte umwandeln (ersetzen Sie T & lt; - & gt; A und C & lt; - & gt; G, erhalten Sie etwas Nützliches:
%Vor%Ich weiß, dass diese Vorverarbeitung kostenintensiv ist und sehr viel Platz beansprucht, aber Sie können anschließend die Standard-String-Algorithmen verwenden und mit der Menge der Vergleiche, die Sie suchen, wird es sicherlich gerechtfertigt sein.
Wenn der ursprüngliche String und der umgekehrte Lookup-String, denke ich, Ihr Problem klingt überraschend ähnlich zu dem längsten gemeinsamen Teilstring > Problem, das gut beschrieben ist. Ihre zweite Vorverarbeitung würde darin bestehen, einen Suffix-Baum zu konstruieren, um ein schnelles Nachschlagen von Teilstrings zu ermöglichen.
Sie werden mit quadratischen Laufzeiten enden, aber ich bezweifle, dass Sie es besser machen können
Die einfachste Lösung wäre, aus den Daten maximaler Höhe maxLen ein Trie zu konstruieren. Jeder Knoten sollte außerdem eine Liste der Speicherorte enthalten, an denen diese bestimmte Zeichenfolge gefunden wurde (in aufsteigender Reihenfolge, wenn der Trie in der richtigen Reihenfolge erstellt wird).
Dann, während Sie suchen, kehren Sie einfach die Suchzeichenfolge zurück und durchlaufen Sie den Trie. Wenn Sie eine Übereinstimmungsüberprüfung finden, ob eine der Übereinstimmungen im richtigen Intervall liegt, geben Sie die Zeichenfolgen aus, wenn 'ja'.
Lassen Sie es mich wissen, wenn Sie den detaillierten Algorithmus benötigen.
Ich würde in Betracht ziehen, die Zeichenfolgen in 16-Bit-Längen in Binärwerte umzuwandeln:
A = 101
T = 010
C = 110
G = 001
Dies ermöglicht bis zu 5 Zeichen pro 16-Bit-Einheit. Dies sollte im Vergleich zu String-Suchen und Vergleichen sehr schnell sein.
Mit dem oberen Bit bestimmen Sie, ob es sich um eine 4-Sequenzeinheit oder 5-Sequenzeinheit handelt.
Jetzt können Sie eine schnelle Sortierung durchführen und alle 4 Sequenz- und 5 Sequenzeinheiten in ihre eigenen Gruppen aufnehmen (es sei denn, Sie müssen 4 Sequenzeinheiten finden, die teilweise gegen 5 Sequenzeinheiten passen).
Für den Vergleich können Sie wieder sortieren, und Sie werden feststellen, dass alle Sequenzen, die mit G beginnen, vor Sequenzen stehen, die mit T beginnen, dann A und dann C. Sie können dann eine Sequenz nehmen und sie mit nur vergleichen Teile des sortierten Arrays, die möglich sind - was ein viel, viel kürzerer Problemraum sein sollte.
Der Grund, warum ich diese drei Bit-Kodierungen für die Sequenzen gewählt habe, ist, dass Sie die beiden Strings einfach xorieren können, um zu sehen, ob sie übereinstimmen. Wenn Sie 15 1 in der Reihenfolge bekommen, dann passen die zwei perfekt zusammen. Wenn nicht, dann nicht.
Sie müssen das antiparallele Bit herausfinden - ich habe ein paar Gedanken dazu, aber das sollte Ihnen den Anfang machen, und wenn der anitparallele Teil ein Problem wird, stellen Sie eine andere Frage.
Tags und Links algorithm c# bioinformatics