Jak zapewne wiesz, w DNA są cztery zasady - adenina ( A), cytozyna ( C), guanina ( G) i tymina ( T). Zwykle Awiązania z Ti Cwiązania z Gtworzącą „szczeble” z podwójną spiralą DNA .

Definiujemy dopełnienie zasady jako bazę, z którą się wiąże - tj. Dopełnienie Ajest T, dopełnienie Tjest A, uzupełnienie Cjest Gi uzupełnienie Gjest C. Możemy również zdefiniować dopełnienie łańcucha DNA jako ciąg z każdą komplementowaną zasadą, np. Dopełnienie GATATCto CTATAG.

Ze względu na dwuniciową strukturę DNA zasady jednej nici są komplementarne do zasad drugiej nici. Jednak DNA ma kierunek, a transkrypcja DNA zachodzi w przeciwnych kierunkach na dwóch niciach. Dlatego biolodzy molekularni są często zainteresowani odwrotnym dopełnieniem łańcucha DNA - całkiem dosłownie odwrotnością dopełniacza łańcucha.

Aby rozszerzyć nasz poprzedni przykład, odwrotne uzupełnienie GATATCjest odwrotne CTATAG, więc GATATC. Jak można zauważyć, w tym przykładzie odwrotne uzupełnienie jest równe pierwotnemu ciągowi - taki ciąg nazywamy odwrotnym palindromem . *

Biorąc pod uwagę ciąg DNA, czy możesz znaleźć najdłuższy substrat, którym jest odwrotny palindrom?

^{* Używam terminu „odwrotny palindrom” zaczerpnięty z Rosalind , aby odróżnić się od zwykłego znaczenia palindromu.}

Wejście

Dane wejściowe będą stanowić pojedynczy ciąg znaków składający się wyłącznie ze znaków ACGTpisanych wielkimi literami. Możesz napisać funkcję lub pełny program dla tego wyzwania.

Wynik

Możesz zdecydować się na wydruk za pośrednictwem drukowania lub zwrotu (ten drugi wybór jest dostępny tylko w przypadku funkcji).

Twój program powinien wypisać najdłuższy odwrotny palindromiczny podciąg ciągu wejściowego, jeśli istnieje unikalne rozwiązanie. Jeśli istnieje wiele rozwiązań, możesz wydrukować dowolne z nich lub wszystkie (według własnego wyboru). Duplikaty są w porządku, jeśli zdecydujesz się wydrukować je wszystkie.

Gwarantowane wejście ma rozwiązanie o długości co najmniej 2.

Przykład działał

ATGGATCCG -> GGATCC

Odwrotnym dopełnieniem GGATCCjest samo ( GGATCC --complement--> CCTAGG --reverse--> GGATCC), podobnie GGATCCjak odwrotny palindrom. GATCjest także odwrotnym palindomem, ale nie jest najdłuższy.

Przypadki testowe

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

Punktacja

To jest kod golfowy, więc wygrywa rozwiązanie w najmniejszej liczbie bajtów.

Pyth, 37 36 28 24 bajtów

ef&}TzqmaCd6T_mx4aCk6Tyz

Jest to bardzo krótka wersja, łącząca wskazówki od FryAmTheEggman i lewą sztuczkę sprawdzania palindromu od Petera.

Działa to jednak tylko z Pyth 3.0.1, który można pobrać z tego linku i działać jak

python3 pyth.py -c "ef&}TzqmaCd6T_mx4aCk6Tyz" <<< "ATTCGATCTATGTAAAGAGG"

(tylko linux bash. W systemie Windows naciśnij Enter zamiast <<<, a następnie wpisz dane wejściowe)

To jest moje poprzednie zgłoszenie - rozwiązanie 28 bajtów

J"ACGT"ef&}TzqTjk_m@_JxJdTyz

Dzięki FryAmTheEggman dla tej wersji. Ten tworzy wszystkie możliwe podzbiory wejściowego łańcucha DNA, filtruje podzbiory pod warunkiem, że podzbiór jest podciągiem wejściowym, a odwrotność transformacji jest równa samemu podzestawowi.

Ze względu na wszelkie możliwe tworzenie podzbiorów zajmuje to więcej pamięci niż odpowiedź Piotra.

To moje pierwsze przesłanie - rozwiązanie 36-bajtowe.

J"ACGT"eolNfqTjk_m@_JxJdTm:zhkek^Uz2

To jest dokładne tłumaczenie mojej odpowiedzi CJam . Miałem nadzieję, że będzie on znacznie mniejszy, ale okazuje się, że brak metody tłumaczenia spowodował, że był prawie podobny rozmiar (wciąż 2 bajty mniejsze)

Wypróbuj online tutaj

GolfScript ( 35 34 bajtów)

]{{..(;\);}%)}do{{6&}%.{4^}%-1%=}?

Do celów testowych możesz użyć

]{{..(;\);}%.&)}do{{6&}%.{4^}%-1%=}?

co dodaje a, .&aby zmniejszyć powielony wysiłek.

Sekcja

]{         # Gather string into an array and do-while...
  {        #   Map over each string in the array
    ..     #     Make a couple of copies of the string
    (;     #     Remove the first character from one of them
    \);    #     Remove the last character from the other
  }%
  )        #   Extract the last string from the array
}do        # Loop until that last string is ''
           # Because of the duplication we now have an array containing every substring
           # of the original string, and if we filter to the first occurrence of each
           # string then they're in descending order of length
{          # Find the first element in the string satisfying the condition...
  {6&}%    #   Map each character in the string to its bitwise & with 6
  .{4^}%   #   Duplicate, and map each to its bitwise ^ with 4
           #   This serves to test for A <-> T, C <-> G
  -1%=     #   Reverse and test for equality
}?

CJam, 39 38 bajtów

Jestem pewien, że można to jeszcze pograć w golfa ...

q:Q,,_m*{~Q<>}%{,~}${_"ACGT"_W%erW%=}=

Pobiera łańcuch DNA ze STDIN i wysyła najdłuższy odwrotny palindromowy DNA do STDOUT

Wypróbuj online tutaj

(Wyjaśnienie wkrótce) (Zapisano 1 bajt dzięki Peterowi)

Python 3, 125 znaków

S=input()
l=[]
while S:
 s=_,*S=S
 while s:l+=[s]*all(x+y in"ATA CGC"for x,y in zip(s,s[::-1]));*s,_=s
print(*max(l,key=len))

Spójrz, nie ma indeksowania! (Cóż, z wyjątkiem odwrócenia łańcucha, to się nie liczy).

Iterowanie po podciągach odbywa się poprzez zdjęcie znaków z przodu i końca przy użyciu przypisania oznaczonego gwiazdką . Zewnętrzna pętla usuwa znaki na początku Si dla każdego takiego sufiksu szapętla wszystkie jego przedrostki, testując je jeden po drugim.

Testowanie odwrotnego palindromu odbywa się za pomocą kodu

all(x+y in"ATA CGC"for x,y in zip(s,s[::-1]))

który sprawdza, czy każdy symbol i jego odpowiednik o odwróconym łańcuchu to jeden z „AT”, „TA”, „CG” i „GC”. Znalazłem również rozwiązanie oparte na zestawie, które jest o jedną postać krótsze, ale traci dwa znaki, gdy wymaga użycia zewnętrznych parens.

set(zip(s,s[::-1]))<=set(zip("ACTG","TGAC"))

Nadal wydaje się, że można go skrócić.

Wreszcie drukowany jest najdłuższy palindrom.

print(*max(l,key=len))

Mam nadzieję, że wyjścia rozdzielone spacjami są OK. Jeśli lista również jest w porządku, gwiazda może zostać usunięta. Zamiast tego próbowałem śledzić biegnące maksimum w pętli, a także wcisnąć wewnętrzne pętle w zrozumienie listy, aby móc wziąć maksimum bezpośrednio bez konstruowania l, i oba okazały się nieco dłuższe. Ale było na tyle blisko, że trudno powiedzieć, które podejście jest rzeczywiście najlepsze.

J (45)

{.@(\:#&.>)@,@(('ACGT'&(|.@]-:[{~3-i.)#<)\\.)

Ta funkcja pobiera ciąg znaków:

   {.@(\:#&.>)@,@(('ACGT'&(|.@]-:[{~3-i.)#<)\\.) 'ATGGATCCG'
┌──────┐
│GGATCC│
└──────┘

Wyjaśnienie:

{.@(\:#&.>)@,@(('ACGT'&(|.@]-:[{~3-i.)#<)\\.) 

              (                          \\.)  for each prefix of each suffix
               (                      #<)      include the argument if,
                        |.@]                      its reverse
                            -:                    is equal to
                'ACGT'&(      [{~3-i.)            the complement
            ,@                                 ravel
   (\:#&.>)@                                   sort by length of item
{.@                                            take the first one   

Perl - 59 bajtów

#!perl -p
$_=$_[~!map$_[length]=$_,/((.)(?R)?(??{'$Q5'^$+.-$+}))/gi]

Licząc shebang jako jeden, dane pochodzą z STDIN.

Przykładowe użycie:

$ echo CTCGCGTTTGCATAACCGTACGGGCGGAACAGTCGGCGGTGCCTCCCAGG | perl dna.pl
CCGTACGG

Python 2 - 177 bajtów

s=raw_input()
r,l,o=range,len(s),[]
for a in[s[i:j+1]for i in r(l)for j in r(i,l)]:q=['TC GA'.index(c)-2for c in a];o+=[a if[-n for n in q][::-1]==q else'']
print max(o,key=len)

Prosta brutalna siła. Faktyczna kontrola „odwrotnej palindromiki” jest jedyną interesującą częścią. Tutaj jest napisane bardziej czytelnie:

check = ['TC GA'.index(c)-2 for c in substring]
if [-n for n in check][::-1] == check:
    # substring is reverse palindromic

Robię to na każdym możliwym podciągu i umieszczam je na liście, jeśli to prawda. Jeśli to fałsz, zamiast tego wstawiam pusty ciąg. Po zakończeniu wszystkich sprawdzeń wypisuję najdłuższy element listy. Użyłem pustego ciągu, ponieważ oszczędza on bajtów przed wstawieniem niczego, ale oznacza również, że program nie będzie się dusił, jeśli nie będzie rozwiązania. Wysyła pustą linię i wychodzi z wdziękiem.