Сходство между сжатыми строками: различия между версиями

Задача вычисления сходства между двумя строками заключается в сравнении двух строк с помощью некоторой метрики оценки. Существуют различные метрики оценки; одной из самых популярных является метрика расстояния Левенштейна (или расстояния редактирования). Стандартное решение для метрики расстояния Левенштейна, предложенное Вагнером и Фишером [13], основано на динамическом программировании. Также широко используются такие метрики оценки, как метрика самой длинной общей подпоследовательности, метрика взвешенного расстояния редактирования и метрика аффинного штрафа за гэп (пропуск в последовательности). Последняя имеет наиболее общий характер и является довольно сложной для работы. В таблице 1 показаны различия между этими четырьмя метриками.

Строка S кодируется по длине серии, если она описывается упорядоченной последовательностью пар <math>(\sigma, i)</math>, часто обозначаемых как <math>\sigma^i</math>, каждая из которых состоит из символа алфавита, <math>\sigma</math>, и целого числа, i. Каждая пара соответствует ''длине серии'' в S, состоящей из i последовательных вхождений a. Например, строка ''aaabbbbbaccccbb'' может быть закодирована в виде <math>a^3 b^4 a^1 c^4 b^2</math> или, что эквивалентно, (a, 3) (b, 4) (a, 1) (c, 4) (b, 2). Пусть A и B – две строки длиной n и m, соответственно, A' и B' – закодированные при помощи длин серий строки A и B, а n' и m' – строк длины A' и B', соответственно.