Comme vous le savez peut-être, dans l' ADN, il existe quatre bases: l'adénine ( A), la cytosine ( C), la guanine ( G) et la thymine ( T). Se Alie généralement à Tet se Clie à G, formant les "échelons" de la structure à double hélice d'ADN .

Nous définissons le complément d'une base comme étant la base à laquelle elle se lie - c'est-à-dire le complément de Ais T, le complément de Tis A, le complément de Cis Get le complément de Gis C. Nous pouvons également définir le complément d'une chaîne d'ADN comme étant la chaîne avec chaque base complémentée, par exemple le complément de GATATCisCTATAG .

Du fait de la structure double brin de l'ADN, les bases d'un brin sont complémentaires des bases de l'autre brin. Cependant, l'ADN a une direction et la transcription de l'ADN se produit dans des directions opposées sur les deux brins. C'est pourquoi les biologistes moléculaires s'intéressent souvent au complément inverse d'une chaîne d'ADN - littéralement à l'inverse du complément de la chaîne.

Pour étendre notre exemple précédent, le complément inverse de GATATCest CTATAGvers l'arrière, donc GATATC. Comme vous l'avez peut-être remarqué, dans cet exemple, le complément inverse est égal à la chaîne d'origine - nous appelons une telle chaîne un palindrome inverse . *

Étant donné une chaîne d'ADN, pouvez-vous trouver la plus longue sous-chaîne qui est un palindrome inversé?

^{* J'utilise le terme "palindrome inversé", tiré de Rosalind , pour me différencier de la signification habituelle de palindrome.}

Contribution

L'entrée sera une chaîne unique composée uniquement des caractères ACGTen majuscules. Vous pouvez écrire une fonction ou un programme complet pour ce défi.

Production

Vous pouvez choisir de sortir via l'impression ou le retour (ce dernier choix n'est disponible que dans le cas d'une fonction).

Votre programme doit générer la sous-chaîne palindromique inverse la plus longue de la chaîne d'entrée, s'il existe une solution unique. Si plusieurs solutions existent, vous pouvez soit en sortir une seule, soit toutes (votre choix). Les doublons sont corrects si vous choisissez de les sortir tous.

L'entrée est garantie d'avoir une solution d'au moins longueur 2.

Exemple travaillé

ATGGATCCG -> GGATCC

Le complément inverse de GGATCCest lui-même ( GGATCC --complement--> CCTAGG --reverse--> GGATCC), tout GGATCCcomme un palindrome inversé.GATCest également un palindome inversé, mais ce n'est pas le plus long.

Cas de test

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

Notation

C'est le golf de code, donc la solution dans le moins d'octets gagne.

Pyth, 37 36 28 24 octets

ef&}TzqmaCd6T_mx4aCk6Tyz

Combinant les conseils de FryAmTheEggman et l'astuce de vérification du palindrome inversé de Peter, il s'agit d'une version super courte.

Cependant, cela ne fonctionne qu'avec Pyth 3.0.1 que vous pouvez télécharger à partir de ce lien et exécuter comme

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

(Linux bash uniquement. Sous Windows, appuyez sur Entrée au lieu de <<< puis tapez l'entrée)

Ceci est ma soumission précédente - solution de 28 octets

J"ACGT"ef&}TzqTjk_m@_JxJdTyz

Merci à FryAmTheEggman pour cette version. Celui-ci crée tous les sous-ensembles possibles de la chaîne d'ADN d'entrée, filtre les sous-ensembles à condition que le sous-ensemble soit une sous-chaîne d'entrée et que l'inverse de la transformation soit égal au sous-ensemble lui-même.

En raison de toutes les créations de sous-ensembles possibles, cela prend encore plus de mémoire que la réponse de Peter.

Ceci est ma première soumission - solution de 36 octets.

J"ACGT"eolNfqTjk_m@_JxJdTm:zhkek^Uz2

Ceci est la traduction exacte de ma réponse CJam . J'espérais que ce serait beaucoup plus petit, mais il s'avère que le manque de méthode de traduction rendait la taille presque similaire (toujours 2 octets plus petits cependant)

Essayez-le en ligne ici

GolfScript ( 35 34 octets)

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

À des fins de test, vous souhaiterez peut-être utiliser

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

ce qui ajoute un .&pour réduire l'effort dupliqué.

Dissection

]{         # 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 octets

Je suis sûr que cela peut être joué plus loin ...

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

Prend la chaîne d'ADN de STDIN et sort l'ADN palindromique inverse le plus long vers STDOUT

Essayez-le en ligne ici

(Explication bientôt) (Enregistré 1 octet grâce à Peter)

Python 3, 125 caractères

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))

Regardez ma, pas d'indexation! (Eh bien, sauf pour inverser la chaîne, cela ne compte pas.)

L'itération sur les sous-chaînes se fait en retirant les caractères de l'avant et de la fin à l'aide d'une affectation étoilée . La boucle externe supprime les caractères pour le début deS , et pour chacun de ces suffixes, sboucle sur tous ses préfixes, les testant un par un.

Le test du palindrome inversé est effectué par le code

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

qui vérifie que chaque symbole et son homologue à chaîne inversée sont l'un de "AT", "TA", "CG" et "GC". J'ai également trouvé une solution basée sur un ensemble pour être plus courte d'un caractère, mais perd deux caractères en exigeant des parens externes lorsqu'elle est utilisée.

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

Cela semble toujours pouvoir être raccourci.

Enfin, le palindrome le plus long est imprimé.

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

J'espère que les sorties séparées par des espaces sont OK. Si une liste aussi bien, l'étoile pourrait être supprimée. J'avais plutôt essayé de suivre le max en cours d'exécution dans la boucle, ainsi que de bourrer les boucles internes dans une compréhension de liste afin de pouvoir prendre le max directement sans construire l, et les deux se sont avérés légèrement plus longs. Mais, il était suffisamment proche pour qu'il soit difficile de dire quelle approche est la meilleure.

J (45)

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

Il s'agit d'une fonction qui prend une chaîne:

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

Explication:

{.@(\:#&.>)@,@(('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 octets

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

En comptant le shebang comme un, l'entrée est prise STDIN.

Exemple d'utilisation:

$ echo CTCGCGTTTGCATAACCGTACGGGCGGAACAGTCGGCGGTGCCTCCCAGG | perl dna.pl
CCGTACGG

Python 2 - 177 octets

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)

Force brute simple. La vérification «palindromique inverse» est la seule partie intéressante. Ici, il est écrit de manière plus lisible:

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

Je fais cela sur toutes les sous-chaînes possibles et les mets dans une liste si c'est vrai. Si c'est faux, j'ai mis une chaîne vide à la place. Lorsque toutes les vérifications sont terminées, je génère l'élément le plus long de la liste. J'ai utilisé une chaîne vide car elle économise des octets au lieu de ne rien y mettre, mais cela signifie également que le programme ne s'étouffera pas s'il n'y a pas de solution. Il génère une ligne vide et se termine normalement.