DNA-zu-Binär-Entfernungsberechnung [geschlossen]

Wenn ich DNA als binäre Werte darstelle, wie kann ich den Abstand zwischen ihnen am besten berechnen?

Also: A = 00, T = 11, G = 01 und C = 10

Die Hamming-Distanz zwischen ATGC und TAAC beträgt 3, ihre binären Darstellungen geben jedoch eine andere Antwort:

Hamming-Distanz von 00110110 und 11000010 = 5.

Was ist die beste Methode zur Entfernungsberechnung, wenn die DNA-Basen auf diese Weise dargestellt werden?

Es ist eine Frage der theoretischen Informatik, nicht der Biologie. Ich stimme für die Schließung. Sie sollten es auf cstheory.SE versuchen .
Stimme @Remi.b zu. Aber bevor Sie uns verlassen, "Warum sollten Sie das tun?" wie der IT-Support zu sagen pflegte.
Stellen Sie diese Frage auf StackOverflow, nicht auf cstheory
Ich habe eine Lösung gefunden, ich werde sie beantworten, wenn Sie sie erneut auf StackOverflow fragen
Dies ist eine relevante Frage für biology.se, denke ich. Der Ausdruck "Was ist die beste Art zu rechnen ..." in der Frage ist jedoch irreführend. Die Frage ist nicht, wie man eine Berechnung durchführt, sondern wie man eine biologische Einheit formal und auf biologisch sinnvolle Weise darstellt. Dies ist eine Frage zur theoretischen Biologie, nicht zu cs.
Ich bin auf dieses Problem gestoßen, als ich MANowaks Buch mit dem Titel Evolutionary Dynamics studierte. Dort führt der Autor das Konzept eines Sequenzraums ein, wobei er John Maynard Smith die „Vorstellung“ davon zuschreibt. Nowaks Diskussion ist sehr oberflächlich und enthält Ihre Frage nicht, und ich habe darauf auch keine Antwort. Aber ich denke, ich kann die Frage etwas klarer stellen.
Ein Sequenzraum ist ein L-dimensionaler Raum für Sequenzen (von DNA oder was auch immer) der Länge L. Jede Sequenz ist ein Punkt in diesem Raum, und die Position des Punktes wird so bestimmt, dass der Wert jeder Position innerhalb der Sequenz die Koordinate von bestimmt die entsprechende Dimension im Sequenzraum. Der Autor schlägt dann die Hamming-Distanz von Sequenzen innerhalb dieses Sequenzraums als Maß für die Ähnlichkeit zwischen Sequenzen vor.
Diese Definitionen machen durchaus Sinn, wenn die Sequenzen binäre Elemente enthalten. Und auch jede Sequenz kann durch eine entsprechende binäre Sequenz dargestellt werden, sagt der Autor, was impliziert, dass der Rest einfach ist, wenn wir die Definitionen auf jede biologische Sequenz erweitern wollen. Dies ist jedoch keine einfache Aufgabe, wie das Beispiel in der Frage zeigt.
Jede Koordinate oder Position in der Folge wird durch 2 Bits dargestellt. Einige der Basen unterscheiden sich jedoch in einem ihrer Bits (z. B. A und G), während sich einige von ihnen (A und T) in beiden Bits unterscheiden. Natürlich kann viel darüber spekuliert werden, wie man es bequem macht, aber soweit ich sehen kann, gibt es keinen offensichtlichen Weg. Eine gute Antwort könnte zum Beispiel einige Beispiele aus der Literatur zur Evolutionsdynamik liefern, wie es gemacht wird.
Eine letzte Anmerkung, dies ist eher eine Frage der Evolutionsdynamik / theoretischen Biologie als eine Frage der Bioinformatik. Es ist relevant, wenn eine formale Repräsentation biologischer Sequenzen (meistens zu Simulationszwecken) benötigt wird. Für praktischere Zwecke zur Berechnung des Abstands zwischen tatsächlichen Sequenzen bietet Jack Aidleys Antwort eine gute Grundlage.
Danke, dass du mir sagst, warum du das wissen willst. Ich stelle mir vor, dass der Vergleich zweier alphabetischer Zeichenfolgen nicht dasselbe ist wie der Vergleich zweier binärer Zeichenfolgen, obwohl Sie eine in eine andere "konvertiert" haben. Welche sollte man für einen evolutionären Vergleich verwenden? Keine Ahnung! Um das zu beantworten, müsste ich die Hanning-Distanz verstehen, um zu entscheiden, ob sie auf das Problem anwendbar ist oder nicht. Also denke ich immer noch, dass Sie einen Informatiker mit etwas Molekulargenetik brauchen, um darüber zu diskutieren.
Die Frage habe ich übrigens nicht gestellt.

Antworten (3)

Am besten wählen Sie eine Distanz, die Ihren Vorstellungen entspricht, anstatt sich unbedingt auf die Hamming-Distanz zu verlassen.

Wenn Sie einfach eine Base-by-Base-Differenz wünschen, berechnen Sie diese ( dies kann hilfreich sein), aber Sie möchten möglicherweise auch eine Differenz, die von der Wahrscheinlichkeit der Mutation zwischen verschiedenen Basen abhängt. In diesem Fall möchten Sie eine Funktion definieren, die die Mutation in a übersetzt Bewerten Sie für jeden Transfer, dh Sie möchten vielleicht eine Desaminierung von 5-Methylcytosin zu Thymin als das wahrscheinlichste Ereignis bewerten. Das Ausdrücken der relativen Wahrscheinlichkeiten verschiedener Mutationen ist kein einfaches Problem, aber es gibt eine Reihe weit verbreiteter Optionen .

Wichtig ist, sicherzustellen, dass Sie die zugrunde liegende Biologie repräsentieren, nicht sicherzustellen, dass Sie die schnellste Implementierung haben. Entscheiden Sie sich zuerst dafür und dann für den Algorithmus, der Ihnen die beste Geschwindigkeit bietet (auch die Entscheidung für diesen Algorithmus ist ein Thema für Stack Overflow, nicht für diesen Stack Exchange).

Diese Kodierung macht keinen Sinn, da sich die Nukleotide nicht im Hamming-Raum befinden . Der Hamming-Abstand zwischen jeweils zwei Nukleotiden ist konstant 1, aber bei der binären Codierung variiert er von 1 bis 2.

Ich zögere, mit Code zu antworten, aber es scheint, dass die Community entschieden hat, dass dies eine angemessene Frage für Biology.SE ist. Also hier ist meine Lösung.

Die Idee ist, die zwei Bits, die jedes Nukleotid darstellen, zu "komprimieren", so dass jedes Nukleotid 0 oder 1 (nicht mehr) zum Abstand beiträgt.

Sie könnten binäre Operationen verwenden, um so etwas zu tun (in Java, aber Sie können die Logik in jeder Sprache anwenden):

int seq1 = 54, seq2 = 194;//ATGC and TAAC
int evenBit = 0xAAAAAAAA, oddBit = 0x55555555;

int pseudoDist = seq1 ^ seq2; //Integer.bitCount(pseudoDist) is 5
int dist = ( (pseudoDist&evenBit)>>1 ) | (pseudoDist&oddBit);
int finalDist = Integer.bitCount(dist);//output 3 not five

Die Idee ist, die Gesamtzahl der unterschiedlichen Bits zu erhalten mit:

seq1 ^ seq2

(pseudoDist&0xAAAAAAAA>>1)Aber Sie können die Bits noch nicht einfach zählen, weil Sie stattdessen die Hamming-Distanz erhalten, also müssen Sie alle Bits, die demselben Nukleotid entsprechen, mit: und auf dasselbe Bit komprimieren pseudoDist&0x55555555. Der erste hält die Bits auf geraden Positionen und der zweite die auf ungeraden Positionen.

Jetzt verwenden Sie evenBits | oddBitsund Sie können die Bits zählen.

Die ursprüngliche Frage verschmilzt mathematische Operationen mit dem Bearbeitungsabstand zwischen zwei Zeichenfolgen. Eine Hamming-Distanz ist ein Maß für die Anzahl der Änderungen, die Sie vornehmen müssen, um eine Saite in eine andere Saite umzuwandeln. Wenn Sie das Alphabet in Binärziffern umwandeln und dann die Zahlen addieren oder subtrahieren, erfahren Sie nicht, wie viele Änderungen erforderlich waren.
@mdperry Die Tatsache, dass Sie es nicht verstehen, macht es nicht ungültig ... Sie sagen, es ist unmöglich, aber haben Sie sich meine Antwort angesehen, haben Sie sie getestet? Schauen Sie, es sagt, dass die Hamming-Distanz zwischen ATGCund TAAC3 ist, was die richtige Antwort ist.
Wenn Ihr Ansatz und Ihre Lösung korrekt sind, sollte es einfach sein, Ihren Code auf die Beispiele auf dieser Seite anzuwenden: en.m.wikipedia.org/wiki/Hamming_distance .
@mdperry Dies ist nicht für eine Zeichenfolge gedacht. Die Tatsache, dass nur vier Zustände möglich sind, ermöglicht es Ihnen, es in 3 Codezeilen zu vereinfachen, die für dieses spezielle Problem funktionieren
Eigentlich stimme ich Ihnen jetzt zu: Mein Kommentar ist falsch, bitte entschuldigen Sie.
DNA-zu-Binär-Entfernungsberechnung [geschlossen]
AntwortenHierDatenschutz-Bestimmungen1y, 0v