względu łańcuch o długości n, jaki byłby (pseudo) losowy próbki m podciągów wielkości K tak, że żaden z próbą podciągów pokrywają? Większość moich skryptów jest w Perlu, ale wystarczy łatwe do opanowania rozwiązanie w dowolnym języku.próbkowanie losowe nie zachodzące na siebie ciągów znaków o długości k
Jeśli istnieje znak, który nie może wystąpić na wejściu, np. X, po prostu:
my $size = 20;
my $count = 20;
my $mark = 'X';
my $input = 'CCACGCATTTTTGTTCATTGTTCTGGCTTCTTACAAGGTTCAGTAGACTTTGTAACACAGTTGTGTCTCTCACAGATTGGCAGATGTTTGGTAAAGGATTGACTTTTCAGCCAACTCATGGGAAAGTGAAATAATGTAAAAAACAGGAAGAATACAGTTTTAGGCCTTTCAAGTGAGGCATGGCTTTCAGCTCTTGGCAAGAACAGGCAAGGAGATGCAAGTTTTAGGACTCTAAGAGGCTAGGCTTTTCAAAGTGCTTCTCTCCCCTTCACCCTCCTTCAGTTACAGCACCAAGCACCACCGAGGTGTTACCTGCAGCCTCACTCTCTACCTGGTTGTGGGATCCTGCCACTTCCTTAACCCACACTGAGTTCCTTGTGGTTCACAGGGTCACACAGAGGGCTGTAGAGATACAAAAGATATATGTGATTTTATATCACCTATCATATGAAGATATATTTATAAAATAGGAAACATATTAACCACTTATCATTTTATATATTTATGGTTTTATGTGTCAAAAATATATTGTTTCATGTATGTATTAAAGGATAAGTATGTATAAGAGGTTTTATAGATGTGTAAAATTATATATTTATACGTATCTTTACAAATTTAAGAATAAAGGAAGGAAAATTCTCAAAGAGGAATTCAGATATCAAGCAGTGCCCTTTGACCAAGAGCCTTGGTTACAACATACCTACAAAAGTGAACTATCATTGAAAGACCTATGGACACTGGATTTCTCTTTCCTTATTTAGAAGGGCAGTCTGTGTCTTGGAAAAGCATACAGTTTGTTGTATCTTGCTGGACAACAGGAGTCA';
if (2*$size*$count-$size-$count >= length($input)) {
die "selection may not complete; choose a shorter length or fewer substrings, or provide a longer input string\n";
}
my @substrings;
while (@substrings < $count) {
my $pos = int rand(length($input)-$size+1);
push @substrings, substr($input, $pos, $size, $mark x $size)
if substr($input, $pos, $size) !~ /\Q$mark/;
}
Bardzo jasna i prosta odpowiedź. Jedno pytanie jednak, jaki jest cel '\ Q' w wyrażeniu regularnym? –
Wygląda na to, że ma dość nieuporządkowaną dystrybucję: http://i.imgur.com/EPLexRr.png. –
w przypadku, gdy ustawisz znak $ na coś takiego jak "|". tak, to powinno być bezstronne (ale nie chce nawet próbować, jeśli zamierzasz zająć dużo więcej niż połowę ciągu znaków). – ysth
To jest podejście rekurencyjne w Pythonie. W każdym kroku losowo wybieraj spośród pozostałych partycji ciągu, a następnie losowo wybierz podciągi o długości k z wybranej partycji. Zastąp tę partycję podziałem partycji na wybranym podciągu. Odfiltruj partycje o długości mniejszej niż k i powtórz. Lista podciągów zwraca się, gdy jest ich m lub nie ma żadnych partycji o długości większej lub równej k.
import random
def f(l, k, m, result=[]):
if len(result) == m or len(l) == 0:
return result
else:
if isinstance(l, str):
l = [l]
part_num = random.randint(0, len(l)-1)
partition = l[part_num]
start = random.randint(0, len(partition)-k)
result.append(partition[start:start+k])
l.remove(partition)
l.extend([partition[:start], partition[start+k:]])
return f([part for part in l if len(part) >= k], k, m, result)
Podziel strunę na próbki o pożądanej długości; być może przez zapełnianie tablicy, a następnie 'my $ rnd = $ array [int rand @array]' –
Myślę, że podchodzę do tego, biorąc pod uwagę, że istnieją znaki 'nm * k', których _nie będzie_używać, oraz' m + 1 'luki, do których mogą się udać. Wybierz długości odstępów "m + 1", aby dodać dokładnie "n-m * k". (W ten sposób nie musisz brać pod uwagę nakładania się). – cjm
Zakładam, że podciągi muszą być ciągłe (inaczej byłoby to bardzo łatwe w przypadku iteratora)? –