Wszystkie k-mers / n-gramów


21

Wprowadzenie

Mieliśmy histogramy i liczymy , ale nie wymieniliśmy ich wszystkich.

Każdego roku Dyalog Ltd. organizuje konkurs studencki. Wyzwanie polega na napisaniu dobrego kodu APL. To jest agnostyczna edycja szóstego problemu tego roku.

Mam wyraźną zgodę na opublikowanie tutaj tego wyzwania od pierwotnego autora konkursu. Możesz to zweryfikować, klikając podany link i kontaktując się z autorem.

Problem

Termin k-mer zazwyczaj odnosi się do wszystkich możliwych podciągów o długości k zawartych w ciągu. W genomice obliczeniowej k-mery odnoszą się do wszystkich możliwych podsekwencji (o długości k ) z odczytu uzyskanego przez sekwencjonowanie DNA. Napisz funkcję / program, który pobiera ciąg ik (długość podłańcucha) i zwraca / wyprowadza wektor k-merów oryginalnego ciągu.

Przykłady

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

k > długość łańcucha? Zwróć nic / pusty wynik:
[4,"AC"][]lub ""lub[""]


4
Czy kolejność produkcji ma znaczenie? Kiedy podciąg występuje wiele razy, czy należy go powtórzyć na wyjściu?
feersum

1
Czy mogę zwrócić ciąg wymaganych podciągów oddzielonych znakami nowej linii zamiast tablicy ciągów, tak jak to ?
Leaky Nun

Czy możemy również wprowadzić i wyprowadzić ciąg znaków jako tablicę znaków (np. ['A', 'T', 'C', 'G']Zamiast "ATCG"?
Adnan

Czy odpowiedzi APL Dyalog są dozwolone w tym wyzwaniu PPCG (ponieważ wyzwanie jest również organizowane przez Dyalog)?
Kritixi Lithos

1
@feersum Zamówienie ma znaczenie, a powtórzenia należy powtarzać. To jest jak przesuwane okno.
Adám

Odpowiedzi:



8

Oktawa, 28 bajtów

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

Wypróbuj online!

W przypadku k> długość łańcucha działa w oknach Octave 4.2.1, ale w tio (Octave 4.0.3) nie działa.

Tworzy indeksy numeryczne kolejnych elementów i indeksuje ciąg według niego.

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



5

Brachylog , 3 bajty

s₎ᶠ

Wypróbuj online!

Okular:

  • Wkład: ["ATCGAAGGTCGT",4]
  • Argument: Z
  • Wydajność: Z = ["ATCG","TCGA","CGAA","GAAG","AAGG","AGGT","GGTC","GTCG","TCGT"]

Jak to działa

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

5

Python 3 ,  47 45 42 bajtów

-3 bajty dzięki ovs (użyj odpakowania Python 3, aby ponownie użyć a[n-1:]na końcu).

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

Funkcja rekurencyjna pobierająca ciąg aoraz długość plasterka ni zwracająca listę plasterków lub pusty ciąg.

a[n-1:]pobiera wycinek bieżącego ciągu od n- tego 1- tego (0-indeksowanego) elementu, aby sprawdzić, czy pozostało wystarczającej liczby elementów (pusty ciąg jest falsey w Pythonie) - jest on krótszy niż odpowiednik len(a)>=n.

  • Jeśli istnieje wystarczająca ilość elementów listy jest zbudowane, [...]z pierwszych nelementów łańcucha, a[:n]i niespakowanego wyniku ponownie wywołaniu funkcji *f(...), z rozkolejkowywana wersją aktualnego wejścia (bez pierwszego elementu) a[1:].

  • Jeśli nie ma wystarczającej liczby elementów, ogon rekurencji zostaje osiągnięty, gdy a[n-1:]jest zwracany (w tym przypadku pusty ciąg znaków).

Wypróbuj online!


45 dla Python 2 lub 3 z:

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

f=lambda a,n:a[n-1:]and[a[:n],*f(a[1:],n)]dla 42 bajtów (Python 3) TIO
od

@ovs, bardzo fajnie, zapytałem, czy jest to dopuszczalne (ponieważ pusty wynik jest łańcuchem, a niepusty wynik jest listą).
Jonathan Allan

4

jot , 2 bajty

,\

To nie jest kompletny program, ale funkcja z operatorem.

Nazwij to tak:

echo 4 ,\ 'ATCGAAGGTCGT'

Wypróbuj online!

Jak to działa

Operator (zwany „koniunkcją”) \(o nazwie „ infix ”) jest używany jako taki:

(x u\ y)stosuje czasownik udo kolejnych części listy y(zwanych infiksami).

W utym przypadku funkcja (zwana „czasownikiem”) jest funkcją, ,która jest prostą funkcją „ dołącz ”:

Tworzy tablicę zawierającą elementy, xpo których następuje elementy y.


3

Mathematica, 21 bajtów

##~StringPartition~1&

Funkcja anonimowa. Bierze ciąg i liczbę (w tej kolejności) jako dane wejściowe i zwraca listę ciągów jako dane wyjściowe.


3

R, 65 61 bajtów

-2 bajty dzięki MickyT

-2 bajty poprzez zmianę indeksowania

zwraca anonimową funkcję.

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

substringprzełącza indeksy (w przeciwieństwie do substrktórych nie ma), a jeśli indeks początkowy jest mniejszy niż 1, 1zamiast tego przyjmuje wartość domyślną , więc sprawdza i zwraca pusty ciąg.

x:n-n+1jest równoważne, 1:(x-n+1)ponieważ :ma pierwszeństwo przed sumami / różnicami

Wypróbuj online!


możesz zaoszczędzić kilka bajtów, function(s,n,x=nchar(s))jeśli(n>x,'',substring(s,1:(x-n+1),n:x))
MickyT

@MickyT, dzięki! Zauważyłem też, że mogę upuścić kilka bajtów, zmieniając obliczenia indeksu
Giuseppe


2

Meduza , 7 bajtów

p
_I
\i

Wypróbuj online!

Jak to działa

W liniowym: p(\(I,i))gdzie pjest drukowany i \pobiera wymagane podciągi.

Ijest nieprzetworzonym pierwszym wejściem, podczas gdy ijest oszacowanym drugim wejściem.

W meduzach każda funkcja i operator otrzymują dwa argumenty, jeden z prawej strony, a drugi z dołu. Tutaj funkcja ppobiera argument z wyniku _, który jest wymagany, jeśli mamy użyć operatora \do uzyskania podłańcuchów.




2

Clojure, 19 bajtów

Cóż to jest przydatne:

#(partition % 1 %2)

Przykłady:

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

2

CJam , 4 bajty

{ew}

Anonimowy blok, który oczekuje argumentów na stosie i pozostawia wynik na stosie po.

Wypróbuj online!

ew jest wbudowany, który robi dokładnie to, co jest wymagane.


5
Mam tylko jedną rzecz do powiedzenia: ew
Adám

2

Siatkówka , 41 38 bajtów

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

Wypróbuj online!

Bierze ciąg i liczy na osobne linie. Pierwsze dwa wiersze są używane do konwersji liczby z dziesiętnej na jednostkową, więc jeśli jednoargumentowe wejście jest dopuszczalne, wówczas liczba bajtów zostanie zmniejszona do 34 31. Edycja: Zapisano 3 bajty dzięki @FryAmTheEggman. Lub, jeśli wolisz, 48-bajtowa wersja, która obsługuje znaki nowego wiersza w ciągu, chociaż powoduje to mylące dane wyjściowe:

.*$
$*
!&`(\S|\s)+(?=[\S\s]*¶(?<-1>.)+(?(1)$.)$)

@KritixiLithos Nie rozumiem, jak twoje rozwiązanie bierze pod uwagę liczbę ...
Neil

Och, przepraszam, że właśnie miałem
pierd

To niekoniecznie działa, jeśli ciąg może zawierać nowy wiersz, więc myślę, że możesz zmienić (?!)na .
FryAmTheEggman

2

Oktawa z pakietem obrazów, 29 bajtów

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

Wypróbuj online!

Wyjaśnienie

Funkcja im2col(m,b)pobiera macierz m, wyodrębnia z niej bloki wielkości bi układa je jako kolumny. Domyślnie bloki przesuwają się (w przeciwieństwie do wyraźnych). Tutaj macierz mjest wektorem wierszowym kodów ASCII ciągu wejściowego s(jest to wykonywane jako +s, który jest krótszy niż standardowy double(s)), a rozmiar bma na [1 n]celu uzyskanie poziomo przesuwnych bloków nelementów.

Wynik jest transponowany (przy użyciu transpozycji złożonej sprzężonej ', która jest krótsza niż transpozycja .') w celu przekształcenia kolumn w wiersze, a następnie jest konwertowany z powrotem na znak char ( [... '']który jest krótszy niż standardowy char(...)).



1

Python 3 , 49 bajtów

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

Wypróbuj online!

Rozwiązanie nierekurencyjne, choć nie krótsze.

Kompatybilny z Python 2.


Możesz upuścić f=, oszczędzając dwa bajty, ponieważ nie używasz fnigdzie indziej. Domyślnie funkcje, które zostały właśnie zadeklarowane i nie są używane, można pozostawić bez nazwy.
Pan Xcoder

1

PHP, 75 bajtów

Wersja online

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

80 bajtów bez podwójnych wartości

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

1

Haskell, 39 bajtów

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

Przykład użycia: 4 # "ABCDEF"-> ["ABCD","BCDE","CDEF"].Wypróbuj online!

Prosta rekurencja, która utrzymuje pierwsze nznaki łańcucha wejściowego i kontynuuje ogon łańcucha, o ile jego długość jest nie mniejsza niż n.


1

Serwer Microsoft Sql, 199 bajtów

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

Sprawdź to.



1

Ułożone , 7 bajtów

infixes

Wypróbuj online!

Dość standardowy. Bez tego wbudowanego staje się 20 bajtów:

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

Który jest:

{%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


1

C # 89 bajtów

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

Wypróbuj online!

Najlepsza metoda, jaką mogłem znaleźć w języku C #, jest w zasadzie taka sama jak Java


1

Rubinowy, 48 46 bajtów

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

Żadnych szczególnych sztuczek, po prostu stabby-lambda definiująca funkcję, która pobiera wymagane podciągi z każdego ważnego punktu początkowego.

Zaoszczędzono dwa bajty, ponieważ wydaje się, że nie ma potrzeby przechowywania lambda.


1

V , 16 bajtów

òÀ|ly0Ïp
"_xòkVp

Obawiam się, że nie bardzo dobrze grałem w golfa, walcząc z „usuń ciąg, jeśli k> len (str)”. Dane wejściowe znajdują się w pliku, k jest argumentem. Gra w golfa przed wyjaśnieniem

Wypróbuj online!


Co się stanie, jeśli nie spróbujesz obsłużyć przypadku k> len (str)?
Adám

W zależności od metody, której używam (w szczególności w tym), po prostu pozostawia ciąg bez
zmian

1

Standardowy ML (mosml), 109 65 61 bajtów

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

Pobiera liczbę i listę znaków (dość powszechna alternatywa dla ciągów znaków w świecie SML). (Naprawdę działa oczywiście na wszystkich listach.)

Stosowanie:

- 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

Dziennik zmian:

  • Tak, istnieje standardowa biblioteka. (-44 bajty)
  • Zmień porównanie i zero na [] zgodnie z sugestią (-4 bajty)

1
Możesz zapisać bajt, zmieniając if length(x)<n thenna if n>length(x)then. Ponieważ jednak SML może obsługiwać ciągi znaków, nie jestem pewien, czy dozwolone jest, aby wymagać explodejuż zastosowania do łańcucha wejściowego.
Laikoni

Również then nil elsemoże być skrócony do then[]else.
Laikoni

@ Laikoni też nie jestem pewien, ale ¯ \ _ (ツ) _ / ¯
L3viathan

Korzystając z innych funkcji bibliotecznych, otrzymałem 68-bajtową wersję, która zajmuje się łańcuchami zamiast list znaków. Również Twoje podejście może zostać skrócony do 54 bajtów: fun f$n=if n>length$then[]else List.take($,n)::f(tl$)n.
Laikoni

1

JavaScript (Firefox 30-57), 51 bajtów

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

64 bajty w ES6:

(s,n,t=s.slice(0,--n))=>[...s.slice(n)].map(c=>(t+=c).slice(~n))
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.