Wie Sie vielleicht wissen, gibt es in der DNA vier Basen - Adenin ( A
), Cytosin ( C
), Guanin ( G
) und Thymin ( T
). Typischerweise A
bindet T
und C
bindet mit G
und bildet die "Sprossen" der DNA-Doppelhelixstruktur .
Wir definieren das Komplement einer Basis als die Basis, an die sie bindet - dh das Komplement von A
is T
, das Komplement von T
is A
, das Komplement von C
is G
und das Komplement von G
is C
. Wir können das Komplement eines DNA-Strings auch als den String definieren, bei dem jede Base komplementiert ist, z. B. das Komplement von GATATC
is CTATAG
.
Aufgrund der doppelsträngigen Struktur der DNA sind die Basen auf einem Strang komplementär zu den Basen auf dem anderen Strang. DNA hat jedoch eine Richtung und die DNA-Transkription erfolgt in entgegengesetzten Richtungen auf den beiden Strängen. Daher interessieren sich Molekularbiologen häufig für das umgekehrte Komplement eines DNA-Strings - im wahrsten Sinne des Wortes das Gegenteil des Komplements des Strings.
Um unser vorheriges Beispiel zu erweitern, ist das umgekehrte Komplement von GATATC
also CTATAG
rückwärts GATATC
. Wie Sie vielleicht bemerkt haben, entspricht in diesem Beispiel das umgekehrte Komplement der ursprünglichen Zeichenfolge - wir nennen eine solche Zeichenfolge ein umgekehrtes Palindrom . *
Können Sie bei einer DNA-Kette den längsten Teilstring finden, der ein umgekehrtes Palindrom ist?
* Ich verwende den Begriff "umgekehrtes Palindrom" aus Rosalind , um mich von der üblichen Bedeutung des Palindroms zu unterscheiden.
Eingang
Die Eingabe ist eine einzelne Zeichenfolge, die nur aus den Zeichen ACGT
in Großbuchstaben besteht. Sie können entweder eine Funktion oder ein vollständiges Programm für diese Herausforderung schreiben.
Ausgabe
Sie können die Ausgabe entweder über Drucken oder Zurückgeben wählen (letztere Option ist nur bei einer Funktion verfügbar).
Ihr Programm sollte den längsten umgekehrten palindromischen Teilstring der Eingabezeichenfolge ausgeben, wenn es eine eindeutige Lösung gibt. Wenn mehrere Lösungen vorhanden sind, können Sie entweder eine einzelne oder alle (nach Ihrer Wahl) ausgeben. Duplikate sind in Ordnung, wenn Sie alle ausgeben möchten.
Der Eingang hat garantiert eine Lösung von mindestens Länge 2.
Gearbeitetes Beispiel
ATGGATCCG -> GGATCC
Das umgekehrte Komplement von GGATCC
ist selbst ( GGATCC --complement--> CCTAGG --reverse--> GGATCC
), ebenso GGATCC
wie ein umgekehrtes Palindrom. GATC
ist auch ein umgekehrter Palindom, aber es ist nicht der längste.
Testfälle
AT -> AT
CGT -> CG
AGCA -> GC
GATTACA -> AT, TA
ATGGATCCG -> GGATCC
CCCCCGGGGG -> CCCCCGGGGG
ACATATATAGACT -> ATATAT, TATATA
ATTCGATCTATGTAAAGAGG -> TCGA, GATC
CGCACGTCTACGTACCTACGTAG -> CTACGTAG
TCAATGCATGCGGGTCTATATGCAT -> ATGCAT, GCATGC [, ATGCAT]
CGCTGAACTTTGCCCGTTGGTAGAACGGACTGATGTGAACGAGTGACCCG -> CG, GC, TA, AT [, GC, CG, CG, CG, CG]
CTCGCGTTTGCATAACCGTACGGGCGGAACAGTCGGCGGTGCCTCCCAGG -> CCGTACGG
Wertung
Dies ist Code Golf, daher gewinnt die Lösung in den wenigsten Bytes.
quelle
Antworten:
Pyth,
37 36 2824 BytesDies ist eine super kurze Version, die die Tipps von FryAmTheEggman und den umgekehrten Palindrom-Check-Trick von Peter kombiniert.
Dies funktioniert jedoch nur mit Pyth 3.0.1, das Sie über diesen Link herunterladen und wie folgt ausführen können
(Nur Linux Bash. Drücken Sie unter Windows die Eingabetaste anstelle von <<< und geben Sie die Eingabe ein.)
Dies ist meine vorherige Einreichung - 28-Byte-Lösung
Vielen Dank an FryAmTheEggman für diese Version. Dieser erstellt alle möglichen Teilmengen der Eingabe-DNA-Zeichenfolge, filtert die Teilmengen unter der Bedingung, dass die Teilmenge eine Teilzeichenfolge der Eingabe ist und die Umkehrung der Transformation gleich der Teilmenge selbst ist.
Aufgrund aller möglichen Teilmengenerstellung nimmt dies noch mehr Speicherplatz in Anspruch als Peters Antwort.
Dies ist meine erste Einreichung - 36-Byte-Lösung.
Dies ist die genaue Übersetzung meiner CJam-Antwort . Ich hatte gehofft, dass dies viel kleiner sein würde, aber es stellte sich heraus, dass die fehlende Übersetzungsmethode die Größe fast gleich machte (obwohl immer noch 2 Bytes kleiner).
Probieren Sie es hier online aus
quelle
Uz
ist äquivalent zuUlz
.J"ACGT"eolNf&}TzqTjk_m@_JxJdTyz
Die Verwendungy
für Teilmengen und das anschließende Herausfiltern von Zeichenfolgen, die keine Teilzeichenfolgen sind,z
ist kürzer :)y
es bereits nach Länge sortiert ist. Sie können einfach tunef...
GolfScript (
3534 Bytes)Zu Testzwecken möchten Sie möglicherweise verwenden
Dies fügt ein hinzu
.&
, um den doppelten Aufwand zu reduzieren.Präparation
quelle
q{]{__(;\);}%~}h]{:c:i6f&_4f^W%=}=
in CJam. Gleiche Größe. Versuchen Sie es nicht im Online-Compiler für etwas, das größer als 7 Längeneingaben istCJam,
3938 BytesIch bin sicher, dass dies weiter Golf gespielt werden kann ...
Nimmt den DNA-String von STDIN und gibt die längste reverse palindromische DNA an STDOUT aus
Probieren Sie es hier online aus
(Erklärung bald) (1 Byte dank Peter gespeichert)
quelle
Python 3, 125 Zeichen
Schau ma, keine Indizierung! (Nun, außer um die Zeichenfolge umzukehren, zählt das nicht.)
Iterieren über die Unterketten wird durch Ausziehen Zeichen von der Vorderseite und am Ende durchgeführt unter Verwendung Stern Zuordnung . Die äußere Schleife entfernt Zeichen für den Anfang
S
unds
schleift für jedes solche Suffix alle Präfixe davon und testet sie nacheinander.Das Testen auf das umgekehrte Palindrom erfolgt durch den Code
Hiermit wird überprüft, ob jedes Symbol und sein Gegenstück mit umgekehrter Zeichenfolge "AT", "TA", "CG" und "GC" sind. Ich fand auch, dass eine satzbasierte Lösung ein Zeichen kürzer ist, aber zwei Zeichen verliert, wenn bei Verwendung äußere Parens benötigt werden.
Dies fühlt sich immer noch so an, als könnte es verkürzt werden.
Schließlich wird das längste Palindrom gedruckt.
Ich hoffe, durch Leerzeichen getrennte Ausgänge sind in Ordnung. Wenn eine Liste auch in Ordnung ist, könnte der Stern entfernt werden. Ich hatte stattdessen versucht, das laufende Maximum in der Schleife zu verfolgen und die inneren Schleifen in ein Listenverständnis zu packen, damit ich das Maximum direkt ohne Konstruktion nehmen konnte
l
, und beide fielen etwas länger aus. Aber es war nah genug, dass es schwer zu sagen ist, welcher Ansatz tatsächlich der beste ist.quelle
J (45)
Dies ist eine Funktion, die eine Zeichenfolge akzeptiert:
Erläuterung:
quelle
Perl - 59 Bytes
Wenn man den Shebang als eins zählt, wird die Eingabe von übernommen
STDIN
.Beispielnutzung:
quelle
Python 2 - 177 Bytes
Einfache rohe Gewalt. Der eigentliche "Reverse Palindromic" Check ist der einzig interessante Teil. Hier steht es besser lesbar:
Ich mache das auf jedem möglichen Teilstring und füge sie in eine Liste ein, wenn es wahr ist. Wenn es falsch ist, gebe ich stattdessen eine leere Zeichenfolge ein. Wenn alle Prüfungen abgeschlossen sind, gebe ich das längste Element der Liste aus. Ich habe eine leere Zeichenfolge verwendet, weil sie Bytes spart, weil nichts eingegeben wird, aber es bedeutet auch, dass das Programm nicht erstickt, wenn es keine Lösung gibt. Es gibt eine leere Zeile aus und wird ordnungsgemäß beendet.
quelle
s=raw_input();r,l,g=range,len(s),'TGCA';print max([a for a in[s[i:j+1]for i in r(l)for j in r(i,l)]if[g[n]for n in[~g.find(c)for c in a]]==list(a)[::-1]],key=len)
. Verwendenfind
Sie auch für Zeichenfolgen überindex
:)