Como você deve saber, no DNA existem quatro bases - adenina ( A
), citosina ( C
), guanina ( G
) e timina ( T
). Tipicamente A
ligações com T
e C
ligações com G
, formando os "degraus" da estrutura de hélice dupla de ADN .
Definimos o complemento de uma base para ser a base à qual ele se liga - ou seja, o complemento de A
é T
, o complemento de T
é A
, o complemento de C
é G
e o complemento de G
é C
. Também podemos definir o complemento de uma sequência de DNA para ser a sequência com cada base complementada, por exemplo, o complemento de GATATC
é CTATAG
.
Por causa da estrutura do DNA de fita dupla, as bases em uma fita são complementares às bases na outra fita. No entanto, o DNA tem uma direção e a transcrição do DNA ocorre em direções opostas nas duas cadeias. Portanto, os biólogos moleculares costumam se interessar pelo complemento inverso de uma cadeia de DNA - literalmente, o inverso do complemento da cadeia.
Para estender nosso exemplo anterior, o complemento inverso de GATATC
é CTATAG
para trás, então GATATC
. Como você deve ter notado, neste exemplo o complemento reverso é igual à string original - chamamos essa string de palíndromo reverso . *
Dada uma sequência de DNA, você consegue encontrar a substring mais longa que é um palíndromo reverso?
* Uso o termo "palíndromo reverso", extraído de Rosalind , para diferenciar do significado usual de palíndromo.
Entrada
A entrada será uma única sequência que consiste apenas nos caracteres ACGT
em maiúsculas. Você pode escrever uma função ou um programa completo para esse desafio.
Resultado
Você pode optar por imprimir via impressão ou retorno (a última opção está disponível apenas no caso de uma função).
Seu programa deve gerar a substring palindrômica reversa mais longa da sequência de entrada, se houver uma solução exclusiva. Se existirem várias soluções, você poderá produzir qualquer uma delas ou todas (sua escolha). As duplicatas são válidas se você optar por produzir todas elas.
A entrada é garantida para ter uma solução de pelo menos comprimento 2.
Exemplo trabalhado
ATGGATCCG -> GGATCC
O complemento reverso de GGATCC
é ele próprio ( GGATCC --complement--> CCTAGG --reverse--> GGATCC
), assim GGATCC
como um palíndromo reverso. GATC
também é um palíndromo reverso, mas não é o mais longo.
Casos de teste
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
Pontuação
Isso é código de golfe, então a solução com o menor número de bytes vence.
fonte
Respostas:
Pitão,
37 36 2824 bytesCombinando as dicas de FryAmTheEggman e o truque de verificação de palíndromo reverso de Peter, esta é uma versão super curta.
No entanto, isso só funciona com o Pyth 3.0.1, que você pode baixar deste link e executar como
(somente linux bash. Nas janelas, pressione Enter em vez de <<< e digite a entrada)
Esta é a minha submissão anterior - solução de 28 bytes
Obrigado a FryAmTheEggman por esta versão. Este cria todos os subconjuntos possíveis da cadeia de DNA de entrada, filtra os subconjuntos com a condição de que o subconjunto seja uma subcadeia de entrada e o inverso da transformação seja igual ao próprio subconjunto.
Devido a toda a criação possível de subconjuntos, isso ocupa ainda mais memória do que a resposta de Peter.
Esta é a minha primeira submissão - solução de 36 bytes.
Esta é a tradução exata da minha resposta CJam . Eu esperava que isso fosse muito menor, mas a falta de método de tradução tornou o tamanho quase semelhante (ainda 2 bytes menor)
Experimente online aqui
fonte
Uz
é equivalente aUlz
.J"ACGT"eolNf&}TzqTjk_m@_JxJdTyz
Usandoy
para subconjuntos e depois filtrando as cordas que não são substrings dez
é mais curto :)y
já está classificado por comprimento. Você pode simplesmente fazeref...
GolfScript (
3534 bytes)Para fins de teste, você pode querer usar
que adiciona um
.&
para reduzir o esforço duplicado.Dissecação
fonte
q{]{__(;\);}%~}h]{:c:i6f&_4f^W%=}=
em CJam. Mesmo tamanho. Não tente no compilador on-line para algo maior que 7 entradas de comprimentoCJam,
3938 bytesEstou certo de que isso pode ser jogado ainda mais ...
Retira a cadeia de DNA de STDIN e gera o DNA palindrômico reverso mais longo para STDOUT
Experimente online aqui
(Explicação em breve) (Salvo 1 byte graças a Peter)
fonte
Python 3, 125 caracteres
Olha ma, sem indexação! (Bem, exceto para reverter a string, isso não conta.)
A iteração sobre as substrings é feita retirando os caracteres da frente e do final usando a atribuição com estrela . O loop externo remove caracteres para o início
S
e, para cada sufixo, faz ums
loop em todos os prefixos dele, testando-os um por um.O teste do palíndromo reverso é feito pelo código
que verifica se cada símbolo e sua contraparte de cadeia reversa são "AT", "TA", "CG" e "GC". Também achei que uma solução baseada em conjunto era um caractere menor, mas perde dois caracteres ao exigir parênteses externos quando usada.
Ainda parece que pode ser reduzido.
Finalmente, o palíndromo mais longo é impresso.
Espero que as saídas separadas por espaço estejam OK. Se uma lista também estiver boa, a estrela pode ser removida. Em vez disso, tentei rastrear o máximo de corrida no loop, além de colocar os loops internos em uma lista de compreensão, para que eu pudesse pegar o máximo diretamente sem construir
l
, e os dois ficaram um pouco mais longos. Mas, foi suficientemente próximo que é difícil dizer qual abordagem é realmente a melhor.fonte
J (45)
Esta é uma função que aceita uma string:
Explicação:
fonte
Perl - 59 bytes
Contando o shebang como um, a entrada é retirada
STDIN
.Uso da amostra:
fonte
Python 2 - 177 bytes
Força bruta simples. A verificação "palindrômica reversa" real é a única parte interessante. Aqui está escrito de forma mais fácil:
Faço isso em todas as subseqüências possíveis e as coloco em uma lista, se for verdade. Se for falso, eu coloquei uma string vazia. Quando todas as verificações são feitas, produzo o elemento mais longo da lista. Eu usei uma string vazia porque economiza bytes e não coloca nada, mas também significa que o programa não engasgará se não houver solução. Ele gera uma linha vazia e sai normalmente.
fonte
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)
. Além disso, para cordas, usarfind
mais deindex
:)