Semua k-mer / n-gram

21

Intro

Kami telah memiliki histogram dan penghitungan , tetapi tidak mencantumkan semuanya.

Setiap tahun, Dyalog Ltd. mengadakan kompetisi siswa. Tantangannya adalah untuk menulis kode APL yang baik . Ini adalah edisi bahasa agnostik dari masalah keenam tahun ini.

Saya memiliki izin eksplisit untuk mengirimkan tantangan ini di sini dari penulis asli kompetisi. Jangan ragu untuk memverifikasi dengan mengikuti tautan yang disediakan dan menghubungi penulis.

Masalah

Istilah k-mer biasanya merujuk pada semua kemungkinan panjang substring k yang terkandung dalam string. Dalam genomik komputasi, k-mers merujuk ke semua kemungkinan berikutnya (dengan panjang k ) dari pembacaan yang diperoleh melalui Sequencing DNA. Tulis fungsi / program yang mengambil string dan k (panjang substring) dan mengembalikan / menampilkan vektor k-mer dari string asli.

Contohnya

[4,"ATCGAAGGTCGT"]["ATCG","TCGA","CGAA","GAAG","AAGG","AGGT","GGTC","GTCG","TCGT"]

k > panjang string? Kembalikan apa-apa / hasil kosong:
[4,"AC"][]atau ""atau[""]

Adm
sumber
4
Apakah urutan output penting? Ketika substring terjadi beberapa kali, haruskah itu diulang dalam output?
feersum
1
Bisakah saya mengembalikan string substring yang diperlukan dipisahkan oleh baris baru, bukan array string, seperti ini ?
Leaky Nun
Bolehkah kita juga memasukkan dan menampilkan string sebagai array karakter (seperti ['A', 'T', 'C', 'G']bukan "ATCG"?
Adnan
Apakah jawaban Dyalog APL diizinkan dalam tantangan PPCG ini (karena tantangan tersebut juga diselenggarakan oleh Dyalog)?
Kritixi Lithos
1
@feersum Order penting, dan pengulangan harus diulang. Ini seperti jendela geser.
Adám

Jawaban:

15

Jelly , 1 byte

Jelly memiliki atom diad byte tunggal untuk operasi ini

Cobalah online! (footer membagi daftar yang dihasilkan dengan baris baru, untuk menghindari representasi yang dicetak.)

Jonathan Allan
sumber
1
Entah bagaimana OP pasti tahu ...
Leaky Nun
1
@ LeakyNun sebenarnya saya tidak.
Adám
8

Oktaf, 28 byte

@(N,s)s((1:N)+(0:nnz(s)-N)')

Cobalah online!

Untuk k> string length berfungsi di Octave 4.2.1-windows tetapi di tio (Octave 4.0.3) tidak berfungsi.

Membuat indeks numerik elemen berurutan dan mengindeks string dengan itu.

s= "ATCGAAGGTCGT"
N = 4
idx = (1:N)+(0:nnz(s)-N)'
 =
    1    2    3    4
    2    3    4    5
    3    4    5    6
    4    5    6    7
    5    6    7    8
    6    7    8    9
    7    8    9   10
    8    9   10   11
    9   10   11   12

s(idx) =

ATCG
TCGA
CGAA
GAAG
AAGG
AGGT
GGTC
GTCG
TCGT
rahnema1
sumber
7

C (GCC pada POSIX), 67 66 63 byte

-3 byte terima kasih kepada @LeakyNun!

f(i,s,j)char*s;{for(;j+i<=strlen(s);puts(""))write(1,s+j++,i);}

Cobalah online!

betseg
sumber
Saya pikir Anda tidak perlu j=0 .
Leaky Nun
@ LeakyNun fungsi harus dapat digunakan kembali. Cobalah online! vs. Coba online!
betseg
Padahal jika saya melakukan ini ...
betseg
1
Anda dapat menggantinya j+i<=strlen(s)dengan hanyas[j+i]
Kritixi Lithos
5

Brachylog , 3 byte

s₎ᶠ

Cobalah online!

Spesifikasi:

  • Memasukkan: ["ATCGAAGGTCGT",4]
  • Argumen: Z
  • Keluaran: Z = ["ATCG","TCGA","CGAA","GAAG","AAGG","AGGT","GGTC","GTCG","TCGT"]

Bagaimana itu bekerja

s₎ᶠ
s    Output is a substring of first element of input,
 ₎   with length specified by second element of input.
  ᶠ  Find all solutions.
Biarawati Bocor
sumber
5

Python 3 ,  47 45 42 byte

-3 byte berkat ovs (gunakan pembongkaran Python 3 untuk digunakan kembali a[n-1:] di bagian ekor.)

f=lambda a,n:a[n-1:]and[a[:n],*f(a[1:],n)]

Fungsi rekursif mengambil string, a dan panjang irisan n,, dan mengembalikan daftar irisan atau string kosong.

a[n-1:]mengambil sepotong string arus dari n-1 th (0-diindeks) elemen selanjutnya untuk menguji apakah ada cukup elemen yang tersisa (string kosong adalah falsey di Python) - ini lebih pendek dari setara len(a)>=n.

  • Jika ada cukup elemen daftar dibangun [...],, dengan nelemen pertama dari string,a[:n] dan hasil membongkar memanggil fungsi lagi *f(...),, dengan versi dequeued dari input saat ini (tanpa elemen pertama) a[1:],.

  • Jika tidak ada cukup elemen, ujung rekursi tercapai ketika a[n-1:]dikembalikan (dalam hal ini string kosong).

Cobalah online!


45 untuk Python 2 atau 3 dengan:

f=lambda a,n:a[n-1:]and[a[:n]]+f(a[1:],n)or[]
Jonathan Allan
sumber
f=lambda a,n:a[n-1:]and[a[:n],*f(a[1:],n)]untuk 42 byte (Python 3) TIO
ovs
@ovs, sangat bagus, saya sudah bertanya apakah ini dapat diterima (karena mereka hasil kosong adalah string, sedangkan hasil yang tidak kosong adalah daftar).
Jonathan Allan
4

J , 2 byte

,\

Ini bukan program yang lengkap, tetapi fungsi dengan operator.

Sebut saja seperti itu:

echo 4 ,\ 'ATCGAAGGTCGT'

Cobalah online!

Bagaimana itu bekerja

Operator (disebut "konjungsi") \(dinamai " infix ") digunakan sebagai berikut:

(x u\ y)berlaku kata kerja uuntuk bagian daftar yang berurutan y(disebut infiks).

Fungsi (disebut "kata kerja") udalam hal ini adalah fungsi ,yang merupakan fungsi " tambahkan " sederhana :

Membuat array berisi item xdiikuti oleh item y.

Biarawati Bocor
sumber
3

Mathematica, 21 byte

##~StringPartition~1&

Fungsi anonim. Mengambil string dan angka (dalam urutan itu) sebagai input dan mengembalikan daftar string sebagai output.

LegionMammal978
sumber
3

R, 65 61 byte

-2 byte terima kasih kepada MickyT

-2 byte dengan mengubah pengindeksan

mengembalikan fungsi anonim.

function(s,n,x=nchar(s))`if`(n>x,'',substring(s,x:n-n+1,n:x))

substringsiklus melalui indeks (yang bertentangan dengan substryang tidak), dan jika indeks awal kurang dari 1, defaultnya adalah 1sebagai gantinya, sehingga memeriksa dan mengembalikan string kosong.

x:n-n+1setara dengan 1:(x-n+1)karena :didahulukan dari jumlah / perbedaan

Cobalah online!

Giuseppe
sumber
Anda dapat menyimpan beberapa byte dengan function(s,n,x=nchar(s))jika(n>x,'',substring(s,1:(x-n+1),n:x))
MickyT
@MickyT, terima kasih! Saya juga memperhatikan saya bisa menjatuhkan beberapa byte dengan mengubah perhitungan indeks
Giuseppe
2

Pyth , 2 byte

.:

Ini bukan program yang lengkap, tetapi fungsi bawaan.

Sebut saja seperti itu:

.:"ATCGAAGGTCGT"4

Cobalah online!

Program lengkap:

.:.*

Cobalah online!

(Ini .*percikan.)

Biarawati Bocor
sumber
Meskipun tidak terlalu penting, .:Fbyte lebih pendek untuk program lengkap.
FryAmTheEggman
2

Ubur-ubur , 7 byte

p
_I
\i

Cobalah online!

Bagaimana itu bekerja

Dalam linear:, di p(\(I,i))mana pcetak dan \mendapatkan substring yang diperlukan

I adalah input pertama sementara mentah i input kedua dievaluasi.

Dalam Ubur-ubur, setiap fungsi dan operator mendapat dua argumen, satu dari kanan, dan satu dari bawah. Di sini, fungsi pmendapatkan argumen dari output _, yang diperlukan jika kita ingin menggunakan operator \untuk mendapatkan substring.

Biarawati Bocor
sumber
2

Python 2 , 54 byte

lambda x,n:map(''.join,zip(*[x[b:]for b in range(n)]))

Cobalah online!

Adnan
sumber
2

Clojure, 19 byte

Nah ini berguna:

#(partition % 1 %2)

Contoh:

(def f #(partition % 1 %2))
(println [(f 4 "ATCGAAGGTCGT")
          (f 4 "abc")])

[((A T C G) (T C G A) (C G A A) (G A A G) (A A G G) (A G G T) (G G T C) (G T C G) (T C G T))
 ()]
NikoNyrh
sumber
2

CJam , 4 byte

{ew}

Blok anonim yang mengharapkan argumen pada stack dan membiarkan hasilnya pada stack setelahnya.

Cobalah online!

ew adalah built-in yang melakukan persis apa yang diperlukan.

Kucing Bisnis
sumber
5
Saya hanya punya satu hal untuk dikatakan: ew
Adám
2

Retina , 41 38 byte

.*$
$*
!&`(.)+(?=.*¶(?<-1>.)+(?(1)¶)$)

Cobalah online!

Mengambil string dan mengandalkan garis yang terpisah. Dua baris pertama digunakan untuk mengubah hitungan dari desimal ke unary, jadi jika input unary dapat diterima maka jumlah byte akan dikurangi menjadi 34 31. Edit: Disimpan 3 byte berkat @FryAmTheEggman. Atau, jika Anda lebih suka, versi 48-byte yang menangani baris baru dalam string, meskipun itu menghasilkan output yang membingungkan:

.*$
$*
!&`(\S|\s)+(?=[\S\s]*¶(?<-1>.)+(?(1)$.)$)
Neil
sumber
@KritixiLithos Saya tidak melihat bagaimana solusi Anda memperhitungkannya ...
Neil
Oh, maaf saya baru saja kentut otak> _ <
Kritixi Lithos
Ini tidak selalu bekerja jika string dapat berisi baris baru, jadi saya pikir Anda dapat mengubah (?!)ke .
FryAmTheEggman
2

Paket Oktaf dengan Gambar, 29 byte

@(s,n)[im2col(+s, [1 n])' '']

Cobalah online!

Penjelasan

Fungsi ini im2col(m,b)mengambil matriks m, mengekstrak blok ukuran bdari itu, dan mengaturnya sebagai kolom. Secara default blok geser (berbeda dengan yang berbeda). Di sini matriks madalah vektor baris kode ASCII dari string input s(ini dilakukan sebagai +s, yang lebih pendek dari standar double(s)), dan ukurannya badalah [1 n]untuk mendapatkan blok geser nelemen secara horizontal .

Hasilnya ditransposisikan (menggunakan kompleks-konjugat transpose ', yang lebih pendek dari transpose .') untuk mengubah kolom menjadi baris, dan kemudian dikonversi kembali ke char ( [... ''], yang lebih pendek dari standar char(...)).

Luis Mendo
sumber
2

OK, 2 byte

':

oK memiliki operator jendela geser !

zgrep
sumber
1

Python 3 , 49 byte

f=lambda a,n:[a[i:i+n]for i in range(len(a)-n+1)]

Cobalah online!

Solusi non-rekursif, meskipun tidak lebih pendek.

Kompatibel dengan Python 2.

Biarawati Bocor
sumber
Anda dapat menjatuhkan f=, menghemat dua byte, karena Anda tidak menggunakan ftempat lain. Secara default, fungsi-fungsi yang baru saja dinyatakan dan tidak digunakan dapat dibiarkan tanpa nama.
Tn. Xcoder
1

PHP, 75 Bytes

Versi Online

for([,$n,$s]=$argv;$i+$n-1<strlen($s);)$r[]=substr($s,$i++,$n);print_r($r);

80 Bytes tanpa nilai ganda

for([,$n,$s]=$argv;$i+$n-1<strlen($s);)$r[$p=substr($s,$i++,$n)]=$p;print_r($r);
Jörg Hülsermann
sumber
1

Haskell, 39 byte

n#s|length s<n=[]|1<2=take n s:n#tail s

Contoh penggunaan: 4 # "ABCDEF"-> ["ABCD","BCDE","CDEF"]. Cobalah online!

Rekursi sederhana yang menjaga nkarakter pertama dari string input dan berlanjut dengan ekor string selama panjangnya tidak kurang dari n.

nimi
sumber
1

Microsoft Sql Server, 199 byte

create function dbo.f(@s nvarchar(max),@ int)returns table as return
with v as(select 2 p,left(@s,@)g where len(@s)>=@ union all
select p+1,substring(@s,p,@)from v where len(@s)>p-2+@)select g from v

Periksa.

Andrei Odegov
sumber
1

PowerShell, 70 byte

$b={$c,$s=$args;[regex]::matches($s,"(?=(.{$c}))")|%{''+$_.groups[1]}}

Cobalah online!

Andrei Odegov
sumber
1

Ditumpuk , 7 byte

infixes

Cobalah online!

Cukup standar. Tanpa builtin ini, itu menjadi 20 byte:

{%x#'y-#+:>y#-#>x\#}

Yang mana:

{%x#'y-#+:>y#-#>x\#}
{%                 }   dyad; first arg: x, second arg: y
  x#'                  length of x (the array)
     y-                minus y (the skew)
       #+              plus 1
         :>            range [x, y]
           y#-         y minus 1
              #>       range from [[x, y], [x, y] + y]
                x\#    get indices from x
Conor O'Brien
sumber
1

MATL , 3 byte

YC!

Cobalah online!

Penjelasan

YC   % Sliding blocks of input string with input size, arranged as columns
!    % Transpose
Luis Mendo
sumber
1

C # 89 byte

void a(string s,int n){for(int i=n;i<=s.Length;)Console.WriteLine(s.Substring(i++-n,n));}

Cobalah online!

Metode terbaik yang bisa saya temukan di C # pada dasarnya sama dengan Java

Skidsdev
sumber
1

Ruby, 48 46 byte

->(s,k){0.upto(s.size-k).map{|i|s[i..i+k-1]}}

Tidak ada trik khusus, hanya stabby-lambda yang mendefinisikan fungsi yang menarik substring yang diperlukan dari setiap titik awal yang valid.

Disimpan dua byte, karena sepertinya tidak ada kebutuhan untuk menyimpan lambda.

Chowlett
sumber
1

V , 16 byte

òÀ|ly0Ïp
"_xòkVp

Tidak terlalu golf, aku takut, berjuang dengan "hapus string jika k> len (str)". Input ada dalam file, k adalah argumen. Golf sebelum penjelasan

Cobalah online!

nmjcman101
sumber
Apa yang terjadi jika Anda tidak mencoba menangani kasing k> len (str)?
Adám
Bergantung pada metode yang saya gunakan (khususnya yang ini), ia hanya meninggalkan string
nmjcman101
1

Standar ML (mosml), 109 65 61 byte

fun f(n,x)=if n>length(x)then[]else List.take(x,n)::f(n,tl x)

Membawa nomor dan daftar karakter (alternatif yang cukup umum untuk string di dunia SML). (Benar-benar berfungsi pada semua daftar tentu saja.)

Pemakaian:

- f(3,explode("ABCDEFGH"));
> val it =
    [[#"A", #"B", #"C"], [#"B", #"C", #"D"], [#"C", #"D", #"E"],
     [#"D", #"E", #"F"], [#"E", #"F", #"G"], [#"F", #"G", #"H"]] :
  char list list
- f(7, explode("ABCD"));
> val it = [] : char list list

Changelog:

  • Benar, ada perpustakaan standar .. (-44 bytes)
  • Ubah perbandingan dan nil menjadi [] seperti yang disarankan (-4 byte)
L3viathan
sumber
1
Anda dapat menyimpan byte dengan mengubah if length(x)<n thenke if n>length(x)then. Namun, karena sangat mungkin bagi SML untuk menangani string, saya tidak yakin itu diizinkan untuk mengharuskan explodesudah diterapkan pada string input.
Laikoni
Juga then nil elsebisa disingkat menjadi then[]else.
Laikoni
@Laikoni juga tidak yakin, tapi ¯ \ _ (ツ) _ / ¯
L3viathan
Menggunakan beberapa fungsi pustaka lain saya mendapatkan versi 68 byte yang berkaitan dengan string, bukan daftar char. Juga pendekatan Anda dapat disingkat menjadi 54 bytes: fun f$n=if n>length$then[]else List.take($,n)::f(tl$)n.
Laikoni
1

JavaScript (Firefox 30-57), 51 byte

(s,n,t='')=>[for(c of s)if((t+=c)[n-1])t.slice(-n)]

64 byte dalam ES6:

(s,n,t=s.slice(0,--n))=>[...s.slice(n)].map(c=>(t+=c).slice(~n))
Neil
sumber