Сравнивая строки одинаковой длины и отмечая различия

Question

Учитывая две строки одинаковой длины, такие, что

s1 = "ACCT"
s2 = "ATCT"

Я хотел бы выяснить позиции, где строки различаются.Итак, я сделал это.(пожалуйста, предложите лучший способ сделать это. Держу пари, что должно быть)

z= seq1.chars.zip(seq2.chars).each_with_index.map{|(s1,s2),index| index+1 if s1!=s2}.compact

z - это массив позиций, в которых две строки различны.В этом случае z возвращает 2

. Представьте, что я добавляю новую строку

s3 = "AGCT"

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

s1.chars.zip(s2.chars,s3.chars)

возвращает массив массивов.Учитывая две строки, я опирался только на сравнение двух символов на равенство, но по мере того, как я добавлял больше строк, он становился подавляющим и по мере того, как строки становились длиннее.* может помочь уменьшить избыточность и вернуть позиции, которые в точности совпадают (непустой подрешеток размера 1).Затем я мог бы распечатать индексы и содержимое подмассивов размером> 1.

s1.chars.zip(s2.chars,s3.chars,s4.chars).each_with_index.map{|item| item.uniq}.each_with_index.map{|a,index| [index+1,a] unless a.size== 1}.compact.map{|h| Hash[*h]}
#=> [{2=>["C", "T", "G"]}]

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

Answer 1

Вот где я бы начал. Я специально использую разные строки, чтобы было легче увидеть различия:

str1 = 'jackdaws love my giant sphinx of quartz'
str2 = 'jackdaws l0ve my gi4nt sphinx 0f qu4rtz'

Чтобы получить символы первой строки:

str1.chars.with_index.to_a - str2.chars.with_index.to_a
=> [["o", 10], ["a", 19], ["o", 30], ["a", 35]]

Чтобы получить символы второй строки:

str2.chars.with_index.to_a - str1.chars.with_index.to_a
=> [["0", 10], ["4", 19], ["0", 30], ["4", 35]]

Будет немного замедляться, когда струны станут больше, но это не будет плохо.

---

РЕДАКТИРОВАТЬ: Добавлено больше информации.

Если у вас есть произвольное количество строк и вам нужно сравнить их все, используйте Array#combination:

str1 = 'ACCT'
str2 = 'ATCT'
str3 = 'AGCT'

require 'pp'

pp [str1, str2, str3].combination(2).to_a
>> [["ACCT", "ATCT"], ["ACCT", "AGCT"], ["ATCT", "AGCT"]]

В приведенном выше выводе вы можете видеть, что combination циклически перебирает массив, возвращая различные комбинации элементов массива размером n.

pp [str1, str2, str3].combination(2).map{ |a,b| a.chars.with_index.to_a - b.chars.with_index.to_a }
>> [[["C", 1]], [["C", 1]], [["T", 1]]]

Используя вывод комбинации, вы можете циклически перемещаться по массиву, сравнивая все элементы друг с другом. Таким образом, в приведенном выше массиве, в паре «ACCT» и «ATCT», «C» была разницей между ними, расположенными в позиции 1 в строке. Аналогично, в «ACCT» и «AGCT» разница снова равна «C» в позиции 1. Наконец, для «ATCT» и «AGCT» это «T» в позиции 1.

Поскольку мы уже видели в более длинных образцах строк, что код будет возвращать несколько измененных символов, это должно довольно приблизить вас.

Answer 2

Раствор 1

strings = %w[ACCT ATCT AGCT]

Сначала объедините строки и сделайте хэш всех позиций для каждого символа.

joined = strings.join
positions = (0...joined.length).group_by{|i| joined[i]}
# => {"A"=>[0, 4, 8], "C"=>[1, 2, 6, 10], "T"=>[3, 5, 7, 11], "G"=>[9]}

Затем сгруппируйте индексы по их соответствующей позиции в каждой строке, удалите те, которые повторяются столько раз, сколько строк. Эта часть является вариантом алгоритма, который предлагает Йорг .

length = strings.first.length
n = strings.length
diff = Hash[*positions.map{|k, v| 
  [k, v.group_by{|i| i % length}.reject{|i, is| is.length == n}.keys]
}]

Это даст что-то вроде:

diff
# => {"A"=>[], "C"=>[1], "T"=>[1], "G"=>[1]}

, что означает, что «A» появляется в одинаковых позициях во всех строках, а «C», «T» и «G» отличаются в позиции 1 (отсчет начинается с 0) строк.

Если вы просто хотите узнать позиции, в которых строки различаются, выполните

diff["G"] + diff["A"] + diff["C"] + diff["T"]
# or diff["G"] + diff["A"] + diff["C"]
# => [1]

Решение 2

Обратите внимание, что, поддерживая массив индексов, где парное сравнение не удается, и продолжая добавлять к нему индексы, будет достаточно сравнения s1 с остальными (s2, s3, ...).

length = s1.length
diff = []
[s2, s3, ...].each{|s| diff += (0...length).reject{|i| s1[i] == s[i]}}

Более подробное объяснение

Пусть

s1 = 'GGGGGGGGG'
s2 = 'GGGCGGCGG'
s3 = 'GGGAGGCGG'

После сравнения s1 и s2 у нас есть набор индексов [3, 6], которые представляют их различия. Теперь, когда мы добавляем s3 к рассмотрению, не имеет значения, сравниваем ли мы его с s1 или с s2, потому что, если s1[i] и s2[i] отличаются, то i уже включено в установите [3, 6], поэтому не имеет значения, отличаются ли они от s3[i] и нужно ли добавить i в набор. С другой стороны, если s1[i] и s2[i] одинаковы, то также не имеет значения, какой из них мы сравниваем с s3[i]. Следовательно, парного сравнения s1 с s2, s3, ... достаточно.

Answer 3

Вы почти наверняка не хотите проводить этот анализ с вашим собственным кодом. Скорее, вы хотите передать его существующему инструменту множественного выравнивания , например Clustal .

Я понимаю, что это не ответ на ваш вопрос, но я надеюсь, что это решение вашей проблемы!