Kürzeste Zeichenfolgen, die im menschlichen Genom nicht vorhanden sind

Welche Länge haben die kürzesten DNA-Stränge, die im Genom einer bekannten Person nicht vorhanden sind, und wie lang sind sie?

Und gibt es eine Online-Datenbank, mit der ich das herausfinden könnte?

Nur für meine persönliche Neugier ... warum? Wie auch immer, die Tatsache, dass nicht das Genom von jedem sequenziert wurde, kann ein Problem darstellen
Ich wollte gerade eine Beschreibung schreiben, wie man das selbst herausfindet, aber nach genauerem Nachdenken klingt das schwierig . Im Wesentlichen müssten Sie eine dynamische Programmierlösung erstellen, aber die Lösung wird immer noch eine exponentielle Laufzeit mit einem großen Exponenten in der Länge der Ergebniszeichenfolge haben (was wir nicht wissen).
Ich würde gerne einen tatsächlichen Algorithmus dafür sehen. Die bisherigen Antworten sind verlockend , bleiben aber recht theoretisch
@KonradRudolph kannst du das in eine Antwort umwandeln und erweitern? Klingt interessant, aber ich würde gerne wissen, warum es so schwer wäre und wie diese Lösung aussehen würde.
@ Richard Eigentlich würde Ilmaris Algorithmus in linearer Zeit funktionieren. Mein Ansatz ging das Problem umgekehrt an, weil ich Allgemeingültigkeit angenommen habe, während Ilmari (korrekterweise) davon ausgeht, dass wir eine Obergrenze für die Länge des nicht vorhandenen Infixes angeben können, was die Verwendung von Nachschlagetabellen ermöglicht. Mein Ansatz hätte den gesamten Suchraum aller möglichen k-Tupes für k = 2… (was exponentiell ist) durchlaufen und überprüft, ob jeder von ihnen einen vorgefertigten Index des Genoms enthält.
Ich denke, Sie können ihre mögliche Länge mit Statistiken zählen. Ich halte es für unmöglich, sie zu finden, weil man nicht die DNA jedes lebenden Menschen überprüfen kann... Es gibt sehr variable Regionen in der DNA, also kann theoretisch jede Kombination dort passieren... Ich denke, die kürzeste Region - wenn es eine solche gibt ein Ding - wird sich auf einige funktionelle Dinge über die DNA-Regulierung beziehen (nicht mein Lieblingsthema), und es wird tödlich sein, wenn es vorhanden ist. ZB wird es Chromosomen brechen oder andere ausgefallene Sachen machen ...

Antworten (3)

Das menschliche Genom enthält weniger als 4 16 -Basenpaare, also muss es selbst nach Einbeziehung eines Faktors von 2 für die beiden Stränge und eines weiteren Faktors, um eine gewisse genetische Variation zu ermöglichen, sicherlich einen 17-Basen-Strang geben, der in keinem der beiden Stränge des Genoms zu finden ist .

Nun, 4 17 Bit sind zwei Gigabyte, was heutzutage problemlos in den Speicher eines typischen Desktop-Computers passt. Ein einfacher und effizienter Algorithmus zum Auffinden einer solchen Zeichenfolge wäre also, ein Array von 4 17 Bit einzurichten und sie alle zu initialisieren Null, und iterieren Sie dann einfach über das gesamte Genom (einschließlich aller bekannten Variationen), nehmen Sie jede 17-Basen-Untersequenz (und ihr Komplement), ordnen Sie sie Ganzzahlen zur Basis 4 zu und setzen Sie die Bits im Array an den Positionen, die durch diese Ganzzahlen gegeben sind zu eins.

Sobald Sie fertig sind, entsprechen alle verbleibenden Null-Bits Zeichenfolgen, die nicht im Genom gefunden werden. Genauer gesagt, der längste aufeinanderfolgende Block von Null-Bits gibt Ihnen die kürzeste Basiszeichenfolge, die nicht im Genom vorhanden ist.

einfach über das gesamte Genom iterieren (einschließlich aller bekannten Variationen) : einfach ist nicht wirklich das Wort, das ich verwendet hätte, aber trotzdem ...
@Ilmari: Was Sie mit Ihrer Methode finden, sind diese 17 Sequenzen, die nicht in einem menschlichen Genom enthalten sind. Aber die Frage bezog sich auf das Genom einer bekannten Person .
@rwst: Die von mir beschriebene Methode kann genauso einfach mehrere Genome oder Fragmente von Genomen verarbeiten und die k-mere finden, die in keinem von ihnen vorhanden sind. Ich bin mir sicher, dass es andere Komplikationen geben müsste, mit denen man sich befassen müsste, um sie auf tatsächliche Genomdaten anzuwenden, aber dies sollte keine große sein.
@nico Dafür gibt es spezielle Datenstrukturen, die es so einfach machen wie das Iterieren über eine einzelne Zeichenfolge (außer dass Sie für jede Position kein einzelnes 17-mer haben, das dort beginnt, sondern eine Liste von 17-mers).
Das ist eine gute Antwort - es gibt sicherlich einige 17mere, die nicht im menschlichen Genom auftauchen. Es ist sicherlich nicht möglich zu sagen, dass ein bestimmtes 17mer in keinem menschlichen Genom auftaucht, zumindest bis wir jede Zelle in den Körpern aller Menschen sequenziert haben (Nicht-Keimbahnmutationen treten zu oft auf). Das klingt hart.
Aus diesem Grund sind DNA-PCR-Primer etwa 20 Basen lang, um die Eindeutigkeit sicherzustellen. Setzt auch den Schmelzpunkt auf eine vernünftigere Temperatur.

Das wäre eigentlich nicht allzu schwer zu finden. Ein gängiger Algorithmus beim Genomaufbau nimmt zunächst DNA-Abschnitte und findet alle vorhandenen Teilstränge der Länge k. (Diese sind als k-mere bekannt, und der Algorithmus erstellt dann die Anordnung basierend darauf, wie sich k-mere überlappen.) Bei einem gegebenen Genom ist es also nicht so schwierig, alle k-mere einer bestimmten Länge zu finden.

Wie Ilmaris Antwort betont, gibt es definitiv k-mere mit 17 Basen, die in einer DNA-Reihe von der Größe des menschlichen Genoms nicht existieren. Angesichts der Menge an repetitiven Inhalten, die in tatsächlichen Genomen vorhanden sind, wird die tatsächliche kürzeste Zeichenfolge mit ziemlicher Sicherheit weniger als 17 Basenpaare betragen.

Selbst wenn Sie eine solche Zeichenfolge angeben, werden Sie nie zu 100 % sicher sein, dass Sie alle menschlichen Genome abgedeckt haben, wie es verlangt wird.

Sequenzen, die nicht in einem Genom vorkommen, werden „Nullomere“ genannt .

Dieser Artikel behauptet, dass es keine 10-bp-Sequenzen gibt , die nicht im menschlichen Genom vorkommen, und 80 11-bp-Sequenzen , die dies nicht tun, und zitiert diese Veröffentlichung .

Hier geht es nur um die proteincodierende Region, aber guter Punkt, es gibt Krankheiten, die durch bestimmte DNA-Sequenzen verursacht werden. ZB Fragiles-X-Syndrom .
Kürzeste Zeichenfolgen, die im menschlichen Genom nicht vorhanden sind
AntwortenHierDatenschutz-Bestimmungen1y, 0v