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

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

0 голосов
/ 15 марта 2011

У меня есть небольшая проблема биоинформатики, которую, я думаю, легко решить.Связанный с "фазированием генотипа".Но я не уверен, как справиться с этим.В приведенной ниже выдержке первый столбец - это идентификаторы, последующие столбцы - бинарные генотипы, помеченные «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)

1 Ответ

2 голосов
/ 15 марта 2011

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

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 из метода.)

...