Seperti yang Anda ketahui, dalam DNA ada empat basa - adenin ( A
), sitosin ( C
), guanin ( G
) dan timin ( T
). Biasanya A
ikatan dengan T
dan C
ikatan dengan G
, membentuk "anak tangga" dari struktur heliks ganda DNA .
Kami mendefinisikan komplemen dari basis sebagai basis yang terikat - yaitu komplemen A
is T
, komplemen T
is A
, komplemen C
is G
dan komplemen G
is C
. Kita juga dapat mendefinisikan komplemen dari string DNA menjadi string dengan masing-masing basis dilengkapi, misalnya komplemen dari GATATC
is CTATAG
.
Karena struktur DNA beruntai ganda, basa pada satu untai saling melengkapi dengan basa pada untai lainnya. Namun DNA memiliki arah, dan transkripsi DNA terjadi dalam arah yang berlawanan pada kedua untaian. Oleh karena itu, para ahli biologi molekuler sering tertarik pada komplemen terbalik dari string DNA - secara harfiah kebalikan dari komplemen string.
Untuk memperpanjang contoh sebelumnya, komplemen kebalikan dari GATATC
yang CTATAG
mundur, jadi GATATC
. Seperti yang mungkin telah Anda perhatikan, dalam contoh ini komplemen balik sama dengan string asli - kami menyebut string semacam itu sebagai palindrom terbalik . *
Diberikan string DNA, dapatkah Anda menemukan substring terpanjang yang merupakan palindrom terbalik?
* Saya menggunakan istilah "reverse palindrome", diambil dari Rosalind , untuk membedakan dari arti palindrome yang biasa.
Memasukkan
Input akan berupa string tunggal yang hanya terdiri dari karakter ACGT
dalam huruf besar. Anda dapat menulis fungsi atau program lengkap untuk tantangan ini.
Keluaran
Anda dapat memilih untuk mencetak melalui pencetakan atau pengembalian (pilihan terakhir hanya tersedia jika fungsi).
Program Anda harus menampilkan substring palindromik mundur terpanjang dari string input, jika ada solusi yang unik. Jika ada beberapa solusi, maka Anda dapat mengeluarkan salah satu dari mereka, atau semuanya (pilihan Anda). Duplikat baik-baik saja jika Anda memilih untuk mengeluarkan semuanya.
Input dijamin memiliki solusi setidaknya panjang 2.
Contoh yang berhasil
ATGGATCCG -> GGATCC
Pelengkap terbalik dari GGATCC
itu sendiri ( GGATCC --complement--> CCTAGG --reverse--> GGATCC
), jadi GGATCC
adalah palindrom terbalik. GATC
juga merupakan palindome terbalik, tetapi bukan yang terpanjang.
Uji kasus
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
Mencetak gol
Ini adalah kode golf, sehingga solusi dalam byte paling sedikit menang.
sumber
Jawaban:
Pyth,
37 36 2824 byteMenggabungkan tips dari FryAmTheEggman dan trik cek balik palindrome dari Peter, ini adalah versi super pendek.
Namun, ini hanya berfungsi dengan Pyth 3.0.1 yang dapat Anda unduh dari tautan ini dan jalankan seperti
(hanya linux bash. Di windows, tekan Enter, bukan <<< lalu ketik input)
Ini adalah pengajuan saya sebelumnya - solusi 28 byte
Terima kasih kepada FryAmTheEggman untuk versi ini. Yang satu ini menciptakan semua himpunan bagian yang mungkin dari string DNA input, menyaring himpunan bagian pada kondisi bahwa subset adalah substring input dan kebalikan dari transformasi sama dengan subset itu sendiri.
Karena semua kemungkinan pembuatan subset, ini membutuhkan lebih banyak memori daripada jawaban Peter.
Ini adalah pengiriman pertama saya - solusi 36 byte.
Ini adalah terjemahan tepat dari jawaban CJam saya . Saya berharap ini akan menjadi jauh lebih kecil tetapi ternyata kurangnya metode penerjemahan membuat ukurannya hampir sama (masih 2 byte lebih kecil)
Cobalah online di sini
sumber
Uz
setara denganUlz
.J"ACGT"eolNf&}TzqTjk_m@_JxJdTyz
Menggunakany
untuk subset dan kemudian menyaring string yang bukan substringz
lebih pendek :)y
sudah diurutkan berdasarkan panjang. Anda bisa melakukannyaef...
GolfScript (
3534 bytes)Untuk tujuan pengujian Anda mungkin ingin menggunakan
yang menambahkan
.&
untuk mengurangi upaya yang digandakan.Pembedahan
sumber
q{]{__(;\);}%~}h]{:c:i6f&_4f^W%=}=
di CJam. Ukuran sama. Jangan coba di kompiler online untuk input yang lebih besar dari 7 panjangCJam,
3938 byteSaya yakin ini bisa bermain golf lebih lanjut ...
Mengambil string DNA dari STDIN dan mengeluarkan DNA palindromik terbalik terpanjang ke STDOUT
Cobalah online di sini
(Penjelasan segera) (Disimpan 1 byte berkat Peter)
sumber
Python 3, 125 karakter
Lihat bu, jangan mengindeks! (Yah, kecuali untuk membalikkan string, itu tidak masuk hitungan.)
Iterasi atas substring dilakukan dengan melepas karakter dari depan dan ujung menggunakan tugas yang berkilau bintangnya . Lingkaran luar menghapus karakter untuk awal
S
, dan untuk setiap akhiran tersebut,s
loop atas semua awalan itu, menguji mereka satu per satu.Pengujian untuk reverse palindrome dilakukan oleh kode
yang memeriksa bahwa setiap simbol dan pasangannya yang dibalik adalah salah satu dari "AT", "TA", "CG", dan "GC". Saya juga menemukan solusi berbasis set menjadi satu karakter lebih pendek, tetapi kehilangan dua karakter karena memerlukan paren luar saat digunakan.
Ini masih terasa seperti bisa dipersingkat.
Akhirnya, palindrom terpanjang dicetak.
Saya berharap keluaran yang dipisahkan ruang OK. Jika daftar juga baik-baik saja, bintang itu dapat dihapus. Saya telah mencoba melacak max berjalan di loop, serta menjejalkan loop batin ke dalam pemahaman daftar sehingga saya bisa mengambil max secara langsung tanpa membangun
l
, dan keduanya ternyata sedikit lebih lama. Tapi, itu cukup dekat sehingga sulit untuk mengatakan pendekatan mana yang terbaik.sumber
J (45)
Ini adalah fungsi yang mengambil string:
Penjelasan:
sumber
Perl - 59 byte
Menghitung shebang sebagai satu, input diambil dari
STDIN
.Penggunaan sampel:
sumber
Python 2 - 177 byte
Kekuatan kasar sederhana. Pemeriksaan "reverse palindromic" yang sebenarnya adalah satu-satunya bagian yang menarik. Di sini tertulis lebih mudah:
Saya melakukan itu pada setiap kemungkinan substring dan memasukkannya ke dalam daftar jika itu benar. Jika itu salah, saya memasukkan string kosong sebagai gantinya. Ketika semua pemeriksaan sudah selesai saya mengeluarkan elemen terpanjang dari daftar. Saya menggunakan string kosong karena menghemat byte daripada meletakkan apa-apa, tetapi itu juga berarti program tidak akan tersedak jika tidak ada solusi. Ini menghasilkan garis kosong dan keluar dengan anggun.
sumber
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)
. Juga, untuk string, gunakanfind
lebih dariindex
:)