Поиск похожих строк в тексте - Фазирование - Динамическое сравнение

Question

У меня есть небольшая проблема биоинформатики, которую, я думаю, легко решить. Связанный с "фазированием генотипа". Но я не уверен, как справиться с этим. В приведенном ниже фрагменте первый столбец представляет собой идентификаторы, последующие столбцы представляют собой бинарные генотипы, помеченные буквой "a" или "b". "-" означает пропущенное значение.

Si_gnF.scaffold10533.53688bp_tag414456 b a a b b a b a a a b a b b a b a a b b a a b b
Si_gnF.scaffold10533.76297bp_tag414484 a b b a a b a b b b a b a a b a b b a - b b a a
Si_gnF.scaffold10533.98416bp_tag414526 a b b a a b a b b b a b a a b a b b a a b b a a
Si_gnF.scaffold10534.48805bp_tag414546 b a a b a b a b b b b b b a a a a b a b b b b a
Si_gnF.scaffold10535.1091787bp_tag414684 a a a b b a a a b a b a a a a b b b a a b b a a
Si_gnF.scaffold10535.1151107bp_tag414765 b b b a a b b b a b a - b b b a a a b b a a b b
Si_gnF.scaffold10535.1220879bp_tag414877 a a a b b a a a b a b a a a a b b b a a b b a a
Si_gnF.scaffold10535.1304464bp_tag414988 b b b a a b b b a b a b b b b a a a b b a a b b
Si_gnF.scaffold10535.1347462bp_tag415047 b b b a a b b b a b a b b b b a a a b b a a b b
Si_gnF.scaffold10535.1379804bp_tag415090 b b b a a b b b a b a b b b b a a a b b a a b b
Si_gnF.scaffold10535.1540335bp_tag415345 a a a b b a a a b a b a a a a b b b a a b b a a
Si_gnF.scaffold10535.1585442bp_tag415410 a a a b b a a a b a b a a a a b b b a a b b a a
Si_gnF.scaffold10535.1609908bp_tag415431 b b b a a b a b a b a b b b b a a a b b a a b b
Si_gnF.scaffold10535.1711158bp_tag415567 b b b a a b b b a b a b b b b a a a b b a a b b
Si_gnF.scaffold10535.1744394bp_tag415609 b b b a a b b b a b a b b b b a a a b b a a b b
Si_gnF.scaffold10535.1751886bp_tag415620 a a a b b a a a b a b a a a a b b b a a b b a a
Si_gnF.scaffold10535.1752774bp_tag415622 a a a b b a a a b a b a a a a b b b a a b b a a
Si_gnF.scaffold10535.1789478bp_tag415675 b b - a a b b b a b a b b b b a a a b b a a b b
Si_gnF.scaffold10535.1800135bp_tag415687 b b b a a b b b a b a b b b b a a a b b a a b b
Si_gnF.scaffold10535.1885424bp_tag415814 a a a b b a a a b a b a a a a b b b a a b b a a

По сути, я хочу минимизировать количество различий между строками. (Я не могу редактировать отдельные столбцы, но могу переворачивать метки на целые строки). Результат для первых четырех строк будет следующим:

Si_gnF.scaffold10533.53688bp_tag414456 b a a b b a b a a a b a b b a b a a b b a a b b
Si_gnF.scaffold10533.76297bp_tag414484 b a a b b a b a a a b a b b a b a a b - a a b b  <-- this one flipped
Si_gnF.scaffold10533.98416bp_tag414526 b a a b b a b a a a b a b b a b a a b b a a b b  <-- this one flipped
Si_gnF.scaffold10533.53688bp_tag414456 b a a b b a b a a a b a b b a b a a b b a a b b

В качестве первого шага мне нужно сделать парные сравнения. Но что является хорошим способом количественной оценки различий, чтобы я знал, для каких строк метки должны быть перевернуты? (2 последовательные строки редко соответствуют 100%; может быть несколько (даже много) несоответствий, а также пропущенные значения).

(в идеале в рубине или R)

Answer 1

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

require 'text' # See http://rubygems.org/gems/text

lines # => a array with each line

def compare(line1, line2)
  Text::Levenshtein.distance(line1.sub(/.*\s/, '').sort,
                             line2.sub(/.*\s/, '').sort)
end

compare(lines[0], lines[1]) # => 1 (one value different)

(Если "a b a a" не равно "a a a b", удалите sort из метода.)