Розалинда: SUBS провалила данное дело

Question

Я написал решение этой проблемы на основе этого ответа. Он успешно обрабатывает приведенный пример, но не фактический.

Вызов:

Учитывая две строки s а также t, t подстрока s если t содержится в виде непрерывного набора символов в s (в следствии, t должно быть не более s).

Положение символа в строке - это общее количество символов, найденных слева от него, включая его самого (например, позиции всех вхождений "U" в "AUGCUUCAGAAAGGUCUUACG" равны 2, 5, 6, 15, 17 и 18).). Символ в положении i из s обозначается s[i],

Подстрока из s может быть представлен как s[j:k], где j а также k представляют начальную и конечную позиции подстроки в s; например, если s = "AUGCUUCAGAAAGGUCUUACG", затем s[2:5] = "UGCU",

Расположение подстроки s[j:k] это его начальная позиция j; Обратите внимание, что t будет иметь несколько мест в s если это происходит более одного раза как подстрока s (см. образец ниже).

Дано:

Две нити ДНК s а также t (каждая длина не более 1 кбп).

Вернуть:

Все места t как подстрока s,

Образец набора данных:

GATATATGCATATACTT
ATAT

Пример вывода:

2 4 10

Для образца это работает. Конечно, вам нужно обрезать форматирование вручную, но это всего лишь пара секунд работы.

Фактические данные и мой сгенерированный вывод не принимаются.

Фактический набор данных:

CAAATAGTCACACAATAGTCGGCTAAATAGTCAATAGTCAAATAGTCAGAGCTAATAGTCTAAATAGTCGAAAAATAGTCATCAATAGTCTAAATAGTCAATAGTCGGAATAGTCAAAATAGTCAATAGTCAATAGTCAATAGTCGACTAAATAGTCCCAATAGTCTCAGAAATAGTCAATAGTCGTAATAGTCAATAGTCTAATAGTCTAATAGTCCAATAGTCTGTCAAATAGTCAATAGTCCAATAGTCGTTTAATAGTCCCCTTTACCAATAGTCAATAGTCCGAATAGTCAGGAATAGTCAGCACTAATAGTCAATAGTCCTAATAGTCCCAATAGTCAAAATAGTCAATAGTCTAAATAATAGTCCTAGCAGAAGAATAGTCTAATAGTCGGCAATAGTCAATAGTCAAATAGTCAGAATAGTCAAATAGTCGAAATAGTCAATAGTCAATAGTCAAATAGTCAAATAGTCAATAGTCAAATAGTCAAATAGTCAAATAGTCGAATAGTCTGTAATAGTCAATAGTCCTTCAATAGTCTAATAGTCATTCAATAGTCAAGAAATAGTCGGGGGAATAGTCCGAATAGTCAAATAGTCAATAGTCGAATAGTCTAATAGTCAATAGTCTAATAGTCTGATAATAGTCAAATAGTCAATAGTCTAAATAGTCGCCTATGCCAATAGTCTTATCAAATAGTCTCTTAATAGTCTAATAGTCAATAGTCAATAGTCTAATAGTCATAATAGTCAATAGTCAAGGAATAGTCCCATAATAGTCAATAGTCTTAATAGTCCAAACGAAATAGTCTTAATAGTCCCTAATAGTCACTAATAGTCGTAATAGTCATAATAGTCCAATAGTCTAAATAGTCTGCAATAGTCAAATAGTCAAATAGTCCGTACAATAGTCTTAATAGTCTTTGCGGCTCAATAGTCTCATAATAGTC
AATAGTCAA

Фактический выход (обрезается):

26 33 93 109 118 125 132

Код:

def find_substring_locations(long, short)
  mpos = []
  re = Regexp.new(short)
  m = i = 0
  m = re.match( long, i ) { |k| j = k.begin(0); i = j + 1; mpos << j } while m
  return mpos
end

def plus_one(input)
  arr = []
  for i in input
    arr << (i += 1)
  end
  arr
end

main_string = gets.chomp
sub_string = gets.chomp
plus_one(find_substring_locations(main_string, sub_string))

Где я неправ? Вроде бы в порядке.

РЕДАКТИРОВАТЬ: Оказывается, проблема была сбой в окружающей среде. После перезагрузки проблема не может быть воспроизведена.

Answer 1

Я думаю, что ваш код является правильным, кроме выключения одной ошибкой. plus_one Решение может быть упрощено.

m = re.match( long, i ) { |k| j = k.begin(0); i = j + 1; mpos << j + 1} while m

Но есть более простой способ реализации. Вам не нужно регулярное выражение, есть более простой способ поиска индекса соответствия подстроки:

String#index принимает дополнительный аргумент, начальный индекс.

input = "CAAATAGTCACACAATAGTCGGCTAAATAGTCAATAGTCAAATAGTCAGAGCTAATAGTCTAAATAGTCGAAAAATAGTCATCAATAGTCTAAATAGTCAATAGTCGGAATAGTCAAAATAGTCAATAGTCAATAGTCAATAGTCGACTAAATAGTCCCAATAGTCTCAGAAATAGTCAATAGTCGTAATAGTCAATAGTCTAATAGTCTAATAGTCCAATAGTCTGTCAAATAGTCAATAGTCCAATAGTCGTTTAATAGTCCCCTTTACCAATAGTCAATAGTCCGAATAGTCAGGAATAGTCAGCACTAATAGTCAATAGTCCTAATAGTCCCAATAGTCAAAATAGTCAATAGTCTAAATAATAGTCCTAGCAGAAGAATAGTCTAATAGTCGGCAATAGTCAATAGTCAAATAGTCAGAATAGTCAAATAGTCGAAATAGTCAATAGTCAATAGTCAAATAGTCAAATAGTCAATAGTCAAATAGTCAAATAGTCAAATAGTCGAATAGTCTGTAATAGTCAATAGTCCTTCAATAGTCTAATAGTCATTCAATAGTCAAGAAATAGTCGGGGGAATAGTCCGAATAGTCAAATAGTCAATAGTCGAATAGTCTAATAGTCAATAGTCTAATAGTCTGATAATAGTCAAATAGTCAATAGTCTAAATAGTCGCCTATGCCAATAGTCTTATCAAATAGTCTCTTAATAGTCTAATAGTCAATAGTCAATAGTCTAATAGTCATAATAGTCAATAGTCAAGGAATAGTCCCATAATAGTCAATAGTCTTAATAGTCCAAACGAAATAGTCTTAATAGTCCCTAATAGTCACTAATAGTCGTAATAGTCATAATAGTCCAATAGTCTAAATAGTCTGCAATAGTCAAATAGTCAAATAGTCCGTACAATAGTCTTAATAGTCTTTGCGGCTCAATAGTCTCATAATAGTC"
query = "AATAGTCAA"

def substring_index(input, query)
  last = 0
  matches = []

  while index = input.index(query, last) do
    matches << index += 1
    last = index
  end
  matches
end


p substring_index(input, query)
# => [26, 33, 93, 109, 118, 125, 132, 172, 188, 231, 273, 312, 337, 346, 400, 407, 424, 441, 448, 455, 463, 471, 478, 486, 494, 520, 557, 589, 597, 620, 646, 654, 718, 725, 749, 756, 778, 882, 890]

Answer 2

На самом деле не ответ, но ваш код работает, как и ожидалось:

s = 'CAAATAGTCACACAATAGTCGGCTAAATAGTCAATAGTCAAATAGTCAGAGCTAATAGTCTAAA'\
    'TAGTCGAAAAATAGTCATCAATAGTCTAAATAGTCAATAGTCGGAATAGTCAAAATAGTCAATA'\
    'GTCAATAGTCAATAGTCGACTAAATAGTCCCAATAGTCTCAGAAATAGTCAATAGTCGTAATAG'\
    'TCAATAGTCTAATAGTCTAATAGTCCAATAGTCTGTCAAATAGTCAATAGTCCAATAGTCGTTT'\
    'AATAGTCCCCTTTACCAATAGTCAATAGTCCGAATAGTCAGGAATAGTCAGCACTAATAGTCAA'\
    'TAGTCCTAATAGTCCCAATAGTCAAAATAGTCAATAGTCTAAATAATAGTCCTAGCAGAAGAAT'\
    'AGTCTAATAGTCGGCAATAGTCAATAGTCAAATAGTCAGAATAGTCAAATAGTCGAAATAGTCA'\
    'ATAGTCAATAGTCAAATAGTCAAATAGTCAATAGTCAAATAGTCAAATAGTCAAATAGTCGAAT'\
    'AGTCTGTAATAGTCAATAGTCCTTCAATAGTCTAATAGTCATTCAATAGTCAAGAAATAGTCGG'\
    'GGGAATAGTCCGAATAGTCAAATAGTCAATAGTCGAATAGTCTAATAGTCAATAGTCTAATAGT'\
    'CTGATAATAGTCAAATAGTCAATAGTCTAAATAGTCGCCTATGCCAATAGTCTTATCAAATAGT'\
    'CTCTTAATAGTCTAATAGTCAATAGTCAATAGTCTAATAGTCATAATAGTCAATAGTCAAGGAA'\
    'TAGTCCCATAATAGTCAATAGTCTTAATAGTCCAAACGAAATAGTCTTAATAGTCCCTAATAGT'\
    'CACTAATAGTCGTAATAGTCATAATAGTCCAATAGTCTAAATAGTCTGCAATAGTCAAATAGTC'\
    'AAATAGTCCGTACAATAGTCTTAATAGTCTTTGCGGCTCAATAGTCTCATAATAGTC'

t = 'AATAGTCAA'

plus_one(find_substring_locations(s, t))
#=> [26, 33, 93, 109, 118, 125, 132, 172, 188, 231, 273, 312, 337, 346,
#    400, 407, 424, 441, 448, 455, 463, 471, 478, 486, 494, 520, 557,
#    589, 597, 620, 646, 654, 718, 725, 749, 756, 778, 882, 890]