|
|
Неточное сопоставление строк
Редакционное расстояние и оптимальное редакционное предписание
Align1°. Определены следующие операции редактирования для строк S1 и S2: I — вставка перед текущим символом S1 текущего символа из S2 и переход к следующему символу S2 (текущий символ S1 не изменяется); D — удаление текущего символа S1 и переход к следующему символу S1 (текущий символ S2 не изменяется), R — замена текущего символа S1 на текущий символ S2, M — «пустая операция», при которой текущие символы S1 и S2 не изменяются (после выполнения операций R и M происходит переход к следующему символу в каждой строке). В начальный момент текущими символами считаются первые символы строк. Строка над алфавитом {I, D, R, M}, обеспечивающая преобразование строки S1 в строку S2, называется редакционным предписанием (или просто предписанием) для данных строк. Дана строка S1, предписание T и два символа: C1 и C2. Получить строку S2, если известно, что при выполнении операции I текущим символом строки S2 всегда оказывается символ C1, а при выполнении операции R — символ C2.
Align2°. Даны строки S1, S2 и T. Строка T содержит только символы I, D, R, M. Проверить, является ли строка T предписанием для строк S1 и S2 (определение предписания приведено в Align1); для этого выполнить операции редактирования из T для строки S1, получив строку S'1. Если T является предписанием, т. е. S'1 = S2, то вывести 0, если не является, то вывести номер первого символа S'1, отличающегося от символа S2 с тем же номером (символы нумеруются от 1), или −1, если символы S'1 и S2 с одинаковыми номерами совпадают, но длины строк S'1 и S2 различны. Проверку выполнять в процессе построения строки S'1.
Align3°. Оптимальным предписанием T для строк S1 и S2 называется предписание (см. Align1), содержащее минимальное количество операций I, D, R (операции M не учитываются). Количество операций I, D, R, входящих в оптимальное предписание, называется редакционным расстоянием между S1 и S2. Даны строки S1, S2 и четыре строки, содержащие только символы I, D, R, M. Известно, что одна из этих четырех строк является оптимальным предписанием для S1 и S2. Вывести редакционное расстояние между S1 и S2 и порядковый номер той строки, которая является оптимальным предписанием.
Align4°. Даны строки S1, S2 и числа k1, k2 (0 ≤ k1 ≤ |S1|, 0 ≤ k2 ≤ |S2|). Через D(i, j), обозначается редакционное расстояние между строками S1[1..i] и S2[1..j] (см. Align3). Справедливы следующие соотношения: • для любого i D(i, 0) = i;
• для любого j D(0, j) = j;
• если i > 0 и j > 0, то D(i, j) = min{D(i − 1, j) + 1, D(i, j − 1) + 1, D(i − 1, j − 1) + t(i, j)}, где t(i, j) = 1, если S1[i] ≠ S2[j], и t(i, j) = 0, если S1[i] = S2[j]. Найти D(k1, k2), используя рекурсивную функцию, выполняющую вычисления по приведенным формулам (так называемая нисходящая рекурсия). Вывести значение D(k1, k2) и количество рекурсивных вызовов функции, которое потребовалось для его вычисления. Примечание. Алгоритм решения задачи оптимизации (в нашем случае вычисления редакционного расстояния D(k1, k2)) путем сведения этой задачи к аналогичной задаче (или набору задач) «меньшего» размера называется алгоритмом динамического программирования.
Align5°. Даны строки S1 и S2. Для эффективного вычисления редакционного расстояния D(|S1|, |S2|) между данными строками по формулам из Align4 можно использовать следующий метод восходящей рекурсии. Вводится в рассмотрение матрица D размера (|S1| + 1) × (|S2| + 1), строчки и столбцы которой нумеруются от 0. Вначале заполняются элементы нулевой строчки и нулевого столбца: D0,j = j, Di,0 = i. Затем выполняется последовательное заполнение по строчкам остальных элементов матрицы; при этом для вычисления очередного элемента Di,j используются уже найденные элементы, расположенные левее (элемент Di,j−1), выше (элемент Di−1,j) и левее и выше (элемент Di−1,j−1) вычисляемого элемента. Элемент, расположенный в последней строчке и последнем столбце, равен редакционному расстоянию. Используя метод восходящей рекурсии, найти матрицу D и вывести элементы ее двух последних строчек: Dn−1,j, j = 0,…, |S2|, Dn,j, j = 0, …, |S2|, где n = |S1|.
Align6°. Даны строки S1 и S2. Дополнить метод восходящей рекурсии (см. Align5) так, чтобы он позволял найти не только редакционное расстояние, но и количество различных оптимальных предписаний. Для этого дополнительно ввести в рассмотрение матрицу K того же размера, что и матрица D, и заполнять эту матрицу синхронно с D по следующим правилам: K0,j = 1, Ki,0 = 1, значение Ki,j при i > 0 и j > 0 равно сумме значений тех элементов Ki,j−1, Ki−1,j, Ki−1,j−1, которые соответствуют элементам матрицы D, дающим минимум в формуле для D(i, j). Элемент, расположенный в последней строчке и последнем столбце матрицы K, равен количеству возможных оптимальных предписаний. Вывести последние строчки матриц D и K.
Align7°. Даны строки S1 и S2 и матрица D, полученная методом восходящей рекурсии (см. Align5). Известно, что имеется единственное оптимальное предписание для S1 и S2. Найти это предписание, выполняя обратный проход по матрице D, начиная с ее правого нижнего элемента и заканчивая левым верхним элементом; при этом для каждого элемента Di,j при i > 0 и j > 0 перемещение выполняется в тот из элементов Di,j−1, Di−1,j, Di−1,j−1, на котором достигается минимум в формуле для D(i, j) (см. Align4), для элементов D0,j перемещение всегда выполняется влево, а для элементов Di,0 — вверх. Перемещение влево соответствует операции I, перемещение вверх — операции D, а перемещение по диагонали влево и вверх — операции R, если S1[i] ≠ S2[j], и операции M, если S1[i] = S2[j] (операции добавляются в предписание справа налево). Вывести найденное оптимальное предписание.
Align8°. Даны строки S1 и S2 и матрица D, полученная методом восходящей рекурсии (см. Align5). Найти один из вариантов оптимального предписания для S1 и S2, выполняя обратный проход по матрице D (см. Align7). Если для некоторого элемента Di,j возможны перемещения более чем в один из его соседних элементов Di,j−1, Di−1,j, Di−1,j−1, то предпочтение отдается перемещению влево (соответствующему операции I), а при его невозможности — перемещению вверх (соответствующему операции D). Вывести найденное оптимальное предписание.
Align9°. Даны строки S1 и S2 и матрица D, полученная методом восходящей рекурсии (см. Align5). Найти все оптимальные предписания для S1 и S2, выполняя обратный проход по матрице D (см. Align7). Если для некоторого элемента Di,j возможны перемещения более чем в один из его соседних элементов Di,j−1, Di-1,j, Di-1,j-1, то использовать следующий порядок перебора допустимых в данной позиции операций: I (перемещение влево), D (перемещение вверх), R или M (перемещение по диагонали). Реализовать один шаг обратного хода в виде рекурсивной функции, количество собственных вызовов которой зависит от числа возможных перемещений в соседние элементы. Вывести все найденные оптимальные предписания (порядок вывода предписаний должен соответствовать порядку их нахождения).
Align10°. Даны строки S1 и S2. Найти редакционное расстояние и один из вариантов оптимального предписания для S1 и S2, используя метод восходящей рекурсии для построения матрицы D (см. Align5) и выполняя обратный проход по матрице D (см. Align7). Выбор варианта оптимального предписания выполнять в соответствии с указаниями Align8.
Align11°. Даны строки S1 и S2. Найти редакционное расстояние и все варианты оптимального предписания для S1 и S2, используя метод восходящей рекурсии для построения матрицы D (см. Align5) и выполняя обратный проход по матрице D (см. Align7 и Align9).
Модификации редакционного расстояния
Align12°. Даны строки S1 и S2. Строки могут содержать особый символ-джокер «?», который считается совпадающим с любым символом. При построении редакционного предписания для строк с джокерами «пустая» операция M может применяться не только при совпадении текущих символов строк, но и в случае, когда один или оба текущих символа являются джокерами. Модифицировать формулы для D(i, j), приведенные в Align4, с учетом дополнительного правила для джокеров и найти редакционное расстояние для S1 и S2, используя метод восходящей рекурсии, описанный в Align5. Вывести элементы двух последних строчек матрицы D: Dn−1,j, j = 0, …, |S2|, Dn,j, j = 0, …, |S2|, где n = |S1| (последний элемент будет равен редакционному расстоянию).
Align13°. Даны строки S1 и S2, которые могут содержать символ-джокер «?» (см. Align12). Дополнить метод восходящей рекурсии (см. Align5) так, чтобы он позволял найти не только редакционное расстояние (с учетом наличия джокеров), но и количество различных оптимальных предписаний. Для этого дополнительно ввести в рассмотрение матрицу K того же размера, что и матрица D, и заполнять эту матрицу синхронно с D по правилам, аналогичным приведенным в Align6. Вывести последние строчки матриц D и K.
Align14°. Даны строки S1 и S2, которые могут содержать символ-джокер «?» (см. Align12), и матрица D, построенная методом восходящей рекурсии (см. Align5) с учетом джокеров. Найти один из вариантов оптимального предписания для S1 и S2, модифицировав алгоритм обратного прохода по матрице D (см. Align7) с учетом наличия джокеров. Выбор варианта оптимального предписания выполнять в соответствии с указаниями Align8.
Align15°. Даны строки S1 и S2, которые могут содержать символ-джокер «?» (см. Align12), и матрица D, построенная методом восходящей рекурсии (см. Align5) с учетом джокеров. Найти все оптимальные предписания для S1 и S2, модифицировав алгоритм обратного прохода, описанный в Align7 и Align9, с учетом наличия джокеров.
Align16°. Даны строки S1 и S2, которые могут содержать символ-джокер «?» (см. Align12). Найти редакционное расстояние и один из вариантов оптимального предписания для S1 и S2, используя модифицированный метод восходящей рекурсии для построения матрицы D (см. Align5) с учетом наличия джокеров и выполняя обратный проход по матрице D (см. Align7). Выбор варианта оптимального предписания выполнять в соответствии с указаниями Align8.
Align17°. Даны строки S1 и S2, которые могут содержать символ-джокер «?» (см. Align12). Найти редакционное расстояние и все варианты оптимального предписания для S1 и S2, используя модифицированный метод восходящей рекурсии для построения матрицы D (см. Align5) с учетом наличия джокеров и выполняя обратный проход по матрице D (см. Align7 и Align9).
Align18°. Даны строки S1 и S2 и положительные числа d и r. Число d определяет вес («стоимость») операций вставки и удаления (I и D), число r — вес операции замены R (вес «пустой» операции M считается равным 0). Оптимальным взвешенным предписанием T для строк S1 и S2 называется предписание, суммарный вес операций в котором является минимальным. Суммарный вес операций, входящих в оптимальное взвешенное предписание, называется редакционно-взвешенным расстоянием между S1 и S2. Через D'(i, j) обозначается редакционно-взвешенное расстояние между строками S1[1..i] и S2[1..j]. Получить рекуррентные формулы для D'(i, j), модифицировав формулы для D(i, j), приведенные в Align4, и найти редакционно-взвешенное расстояние для S1 и S2, применив к матрице D' метод восходящей рекурсии (ср. с Align5). Вывести элементы двух последних строчек матрицы D': D'n−1,j, j = 0, …, |S2|, D'n,j, j = 0, …, |S2|, где n = |S1| (последний элемент будет равен редакционно-взвешенному расстоянию). Примечание. Поскольку операция замены R может быть сведена к последовательному выполнению операций вставки I и удаления D, вес r должен быть меньше удвоенного веса d; в противном случае либо все оптимальные взвешенные предписания не будут содержать операцию R (при r > 2d), либо любое оптимальное взвешенное предписание можно будет преобразовать к виду, не содержащему R (при r = 2d).
Align19°. Даны строки S1 и S2 и положительные числа d и r. Дополнить метод восходящей рекурсии (см. Align18) так, чтобы он позволял найти не только редакционно-взвешенное расстояние, но и количество различных оптимальных взвешенных предписаний. Для этого дополнительно ввести в рассмотрение матрицу K' того же размера, что и матрица D', и заполнять эту матрицу синхронно с D' по правилам, аналогичным приведенным в Align6. Вывести последние строчки матриц D' и K'.
Align20°. Даны строки S1 и S2, положительные числа d, r и матрица D', построенная методом восходящей рекурсии (см. Align18). Найти одно из оптимальных взвешенных предписаний для S1 и S2, используя алгоритм обратного прохода по матрице D' (ср. с Align7). Выбор варианта оптимального предписания выполнять в соответствии с указаниями Align8.
Align21°. Даны строки S1 и S2, положительные числа d, r и матрица D', построенная методом восходящей рекурсии (см. Align18). Найти все оптимальные взвешенные предписания для S1 и S2, применив к матрице D' алгоритм обратного прохода, описанный в Align7 и Align9.
Align22°. Даны строки S1 и S2 и положительные числа d и r. Найти редакционно-взвешенное расстояние и один из вариантов оптимального взвешенного предписания для S1 и S2, используя модифицированный метод восходящей рекурсии для построения матрицы D' (см. Align18) и выполняя обратный проход по матрице D' (см. Align7). Выбор варианта оптимального взвешенного предписания выполнять в соответствии с указаниями Align8.
Align23°. Даны строки S1 и S2 и положительные числа d и r. Найти редакционно-взвешенное расстояние и все варианты оптимального взвешенного предписания для S1 и S2, используя модифицированный метод восходящей рекурсии для построения матрицы D' (см. Align18) и выполняя обратный проход по матрице D' (см. Align7 и Align9).
Глобальное выравнивание строк
Align24°. Глобальным выравниванием двух строк называется результат их преобразования, которое заключается во вставке в них пробелов (возможно, и на концах) и размещении получившихся строк друг над другом таким образом, чтобы каждый символ или пробел одной строки располагался напротив символа или пробела другой строки. Выравнивание, содержащее минимальное число пар несовпадающих символов (в том числе пар «символ–пробел»), называется оптимальным редакционным выравниванием. Даны строки S1, S2 и строка T — один из вариантов оптимального предписания (см. Align3). Построить строки A1 и A2, реализующие оптимальное редакционное выравнивание строк S1 и S2 на основе предписания T, выполняя следующие преобразования: если очередной операцией предписания T является вставка (I), то к A1 добавляется пробел, а к A2 — текущий символ S2; если очередной операцией является удаление (D), то пробел добавляется к A2, а к A1 — текущий символ S1; в случае операции замены (R) и «пустой» операции (M) к A1 и A2 добавляются текущие символы S1 и S2 соответственно (таким образом, операция замены соответствует размещению на одном уровне различных символов строк S1 и S2, а «пустая» операция — размещению на одном уровне одинаковых символов). После вставки текущего символа какой-либо строки текущим становится следующий символ этой строки. Вывести полученные строки A1 и A2.
Align25°. Даны строки S1 и S2. Найти один из вариантов оптимального предписания для данных строк, используя метод восходящей рекурсии для построения матрицы D (см. Align5) и выполняя обратный проход по матрице D (см. Align7). Выбор варианта оптимального предписания выполнять в соответствии с указаниями Align8. Построить на основе найденного предписания оптимальное редакционное выравнивание (A1, A2) (см. Align24) и вывести найденное выравнивание.
Align26°. Даны строки S1 и S2. Найти все варианты оптимального предписания для данных строк, используя метод восходящей рекурсии для построения матрицы D (см. Align5) и выполняя обратный проход по матрице D (см. Align7 и Align9). Построить на основе каждого найденного предписания оптимальное редакционное выравнивание (A1, A2) (см. Align24). Вывести все найденные выравнивания (A1, A2) в порядке, соответствующем порядку нахождения оптимальных предписаний.
Align27°. Даны строки S1 и S2, которые могут содержать символ-джокер «?» (см. Align12). Найти один из вариантов оптимального предписания для данных строк, используя модифицированный метод восходящей рекурсии для построения матрицы D (см. Align5) с учетом наличия джокеров и выполняя обратный проход по матрице D (см. Align7). Выбор варианта оптимального предписания выполнять в соответствии с указаниями Align8. Построить на основе найденного предписания оптимальное редакционное выравнивание (A1, A2) (см. Align24) и вывести найденное выравнивание.
Align28°. Даны строки S1 и S2, которые могут содержать символ-джокер «?» (см. Align12). Найти все варианты оптимального предписания для данных строк, используя метод восходящей рекурсии для построения матрицы D (см. Align5) с учетом наличия джокеров и выполняя обратный проход по матрице D (см. Align7 и Align9). Построить на основе каждого найденного предписания оптимальное редакционное выравнивание (A1, A2) (см. Align24). Вывести все найденные выравнивания (A1, A2) в порядке, соответствующем порядку нахождения оптимальных предписаний.
Align29°. Пусть Σ — алфавит, используемый для строк S1 и S2, Σ' — алфавит Σ, дополненный пробелом. Для x, y из Σ' через s(x, y) (= s(y, x)) обозначается оценка x и y — целочисленный вес пары символов x и y при их выравнивании друг напротив друга. Симметричная матрица, элементами которой являются значения s(x, y), называется матрицей оценок. Если (A1, A2) — некоторое выравнивание строк S1 и S2 (см. Align24), то полная оценка выравнивания определяется как сумма всех оценок s(A1[i], A2[i]), i = 1, …, |A1|. Дано выравнивание (A1, A2) и число m (< 10); алфавит представляет собой m первых строчных латинских букв. Также дана матрица оценок (порядка m + 1), в которой строчки и столбцы соответствуют латинским буквам, расположенным в алфавитном порядке, а пробел соответствует последней строчке и столбцу (в силу симметричности матрицы оценок приводится только ее верхняя треугольная часть, т. е. элементы, лежащие на главной диагонали и выше нее). Найти полную оценку данного выравнивания. Примечание. В матрице оценок элементы, лежащие на главной диагонали, как правило, неотрицательны, а остальные элементы отрицательны; таким образом, наличие пробелов или несовпадающих символов в выравнивании приводит к уменьшению полной оценки выравнивания за счет «штрафов», связанных с пробелами и несовпадениями. При этом оценка для непробельных символов x, y обычно больше суммарной оценки за два пробела, расположенных напротив этих символов: s(x, y) > s(x, _) + s(_, y) (символ «_» обозначает пробел); иными словами, штраф за выравнивание различных символов меньше штрафа за добавление пробелов напротив этих символов).
Align30°. Оптимальным оценочным выравниванием строк S1 и S2 (или просто оптимальным выравниванием) называется любое выравнивание, имеющее максимальную полную оценку (определение оценки приведено в Align29). При этом сама максимальная полная оценка называется сходством строк S1 и S2. Даны строки S1, S2 и числа k1, k2 (0 ≤ k1 ≤ |S1|, 0 ≤ k2 ≤ |S2|). Кроме того, дано число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, и матрица оценок (структура матрицы описана в Align29). Через V(i, j) обозначается сходство строк S1[1..i] и S2[1..j]. Справедливы следующие соотношения (символ подчеркивания «_» обозначает пробел): • для любого i V(i, 0) = Σk=1,…,is(S1[k], _);
• для любого j V(0, j) = Σk=1,…,js(_, S2[k]);
• если i > 0 и j > 0, то V(i, j) = max{V(i − 1, j) + s(S1[i], _), V(i, j − 1) + s(_, S2[j]), V(i − 1, j − 1) + s(S1[i], S2[j])}. Найти V(k1, k2), используя рекурсивную функцию, выполняющую вычисления по приведенным формулам (так называемая нисходящая рекурсия). Вывести значение V(k1, k2) и количество рекурсивных вызовов функции, которое потребовалось для его вычисления. Примечание. Редакционное расстояние для двух строк (см. Align3) служит мерой различия этих строк (более «близкие» строки имеют меньшее редакционное расстояние). В противоположность этой характеристике, значение сходства строк будет тем больше, чем более «близкими» будут строки. В ряде алгоритмов (в частности, при локальном выравнивании строк) оказывается более удобным использовать меру сходства, чем меру различия. Приведенный алгоритм, как и алгоритм нахождения редакционного расстояния (см. Align4), является алгоритмом динамического программирования.
Align31°. Даны строки S1 и S2. Кроме того, дано число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, и матрица оценок (структура матрицы описана в Align29). Для эффективного вычисления сходства строк V(|S1|, |S2|) по формулам из Align30 можно использовать метод восходящей рекурсии, основанный на последовательном вычислении элементов вспомогательной матрицы V размера (|S1| + 1) × (|S2| + 1) (действия при заполнении матрицы V аналогичны действиям при заполнении матрицы D, описанным в Align5). Элемент, расположенный в последней строчке и последнем столбце матрицы V, определяет значение сходства данных строк. Используя метод восходящей рекурсии, найти матрицу V и вывести элементы ее двух последних строчек: Vn−1, j, j = 0, …, |S2|, Vn, j, j = 0, …, |S2|, где n = |S1|.
Align32°. Даны строки S1 и S2. Кроме того, дано число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, и матрица оценок (структура матрицы описана в Align29). Дополнить метод восходящей рекурсии (см. Align31) так, чтобы он позволял найти не только значение сходства строк, но и количество различных вариантов оптимального выравнивания. Для этого дополнительно ввести в рассмотрение матрицу K того же размера, что и матрица V, и заполнять эту матрицу синхронно с V по следующим правилам: K0,j = 1, Ki,0 = 1, значение Ki,j при i > 0 и j > 0 равно сумме значений тех элементов Ki,j−1, Ki−1,j, Ki−1,j−1, которые соответствуют элементам матрицы V, дающим максимум в формуле для V(i, j). Элемент, расположенный в последней строчке и последнем столбце матрицы K, равен количеству вариантов оптимального выравнивания. Вывести последние строчки матриц V и K.
Align33°. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, и матрица оценок (структура матрицы описана в Align29). Кроме того, дана матрица V, полученная методом восходящей рекурсии (см. Align31). Известно, что имеется единственный вариант оптимального выравнивания для S1 и S2. Найти это выравнивание (A1, A2), выполняя обратный проход по матрице V, начиная с ее правого нижнего элемента и заканчивая левым верхним элементом; при этом для каждого элемента Vi,j при i > 0 и j > 0 перемещение выполняется в тот из элементов Vi,j−1, Vi−1,j, Vi−1,j−1, на котором достигается максимум в формуле для V(i, j) (см. Align30); для элементов V0,j перемещение всегда выполняется влево, а для элементов Vi,0 — вверх. Перемещение влево соответствует вставке пробела в строку A1 и текущего элемента S2 в строку A2, перемещение вверх — вставке пробела в строку A2 и текущего элемента S1 в строку A1, перемещение по диагонали влево и вверх соответствует вставке в A1 и A2 текущих элементов S1 и S2 соответственно (символы в строках S1 и S2 перебираются с конца, строки A1 и A2 заполняются от конца к началу). Вывести найденные строки A1 и A2.
Align34°. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, и матрица оценок (структура матрицы описана в Align29). Кроме того, дана матрица V, полученная методом восходящей рекурсии (см. Align31). Найти один из вариантов оптимального выравнивания для S1 и S2, выполняя обратный проход по матрице V (см. Align33). Если для некоторого элемента Vi,j возможны перемещения более чем в один из его соседних элементов Vi,j−1, Vi−1,j, Vi−1,j−1, то предпочтение отдается перемещению влево (соответствующему вставке пробела в первую строку), а при его невозможности — перемещению вверх (соответствующему вставке пробела во вторую строку). Вывести найденное выравнивание (A1, A2).
Align35°. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, и матрица оценок (структура матрицы описана в Align29). Кроме того, дана матрица V, полученная методом восходящей рекурсии (см. Align31). Найти все варианты оптимального выравнивания для S1 и S2, выполняя обратный проход по матрице V (см. Align33). Если для некоторого элемента Vi,j возможны перемещения более чем в один из его соседних элементов Vi,j−1, Vi−1,j, Vi−1,j−1, то использовать следующий порядок перебора допустимых в данной позиции действий: вставка пробела в первую строку и текущего символа во вторую строку (перемещение влево), вставка пробела во вторую строку и текущего символа в первую строку (перемещение вверх), вставка текущих символов в обе строки (перемещение по диагонали). Реализовать один шаг обратного хода в виде рекурсивной функции, количество собственных вызовов которой зависит от числа возможных перемещений в соседние элементы. Вывести все найденные оптимальные выравнивания (порядок вывода выравниваний должен соответствовать порядку их нахождения).
Align36°. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, и матрица оценок (структура матрицы описана в Align29). Найти значение сходства и один из вариантов оптимального выравнивания для S1 и S2, используя метод восходящей рекурсии для построения матрицы V (см. Align31) и выполняя обратный проход по матрице V (см. Align33). Выбор варианта оптимального выравнивания выполнять в соответствии с указаниями Align34.
Align37°. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, и матрица оценок (структура матрицы описана в Align29). Найти значение сходства и все варианты оптимального выравнивания для S1 и S2, используя метод восходящей рекурсии для построения матрицы V (см. Align31) и выполняя обратный проход по матрице V (см. Align33). Перебор вариантов оптимального выравнивания выполнять в соответствии с указаниями Align35.
Модификации глобального выравнивания
Align38°. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, и матрица оценок (структура матрицы описана в Align29). Найти значение сходства для строк S1 и S2 (см. Align30) при дополнительном предположении, что все граничные пробелы являются «бесплатными», т. е. имеют нулевую оценку (под граничными пробелами понимаются пробелы, появившиеся в начале и конце любой из строк в результате их выравнивания). Если через V'(i, j) обозначить сходство строк S1[1..i] и S2[1..j] при условии бесплатных начальных пробелов, то рекуррентные формулы для V'(i, j) будут аналогичны формулам для V(i, j), приведенным в Align30; необходимо лишь изменить базовые условия, положив для любого i V'(i, 0) = 0 и для любого j V'(0, j) = 0. Для эффективного нахождения значений V'(i, j) следует использовать метод восходящей рекурсии, основанный на последовательном вычислении элементов вспомогательной матрицы V' размера (|S1| + 1) × (|S2| + 1) (действия при заполнении матрицы V' аналогичны действиям при заполнении матрицы D, описанным в Align5). Чтобы учесть условие бесплатности конечных пробелов, в качестве значения сходства для строк S1 и S2 следует выбрать наибольшее значение среди элементов матрицы V', расположенных в ее последней строчке или последнем столбце. Вывести найденное значение сходства для S1 и S2, а также элементы последней строчки и последнего столбца матрицы V': V'n,j, j = 0, …, p, V'i,p, i = 0, …, n, где n = |S1|, p = |S2|. Примечание. Бесплатность граничных пробелов приводит к тому, что при оптимальном оценочном выравнивании одна строка будет иметь тенденцию выравниваться по внутренней части другой или суффикс одной строки — по префиксу другой. Таким образом, указанное дополнительное условие следует применять, если требуется распознать ситуацию, при которой одна строка содержит подстроку, «близкую» другой строке, или суффикс одной строки «близок» префиксу другой.
Align39°. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, и матрица оценок (структура матрицы описана в Align29). Кроме того, дана матрица V', полученная методом восходящей рекурсии (см. Align38). Найти один из вариантов оптимального выравнивания для S1 и S2 при условии бесплатных граничных пробелов, модифицировав требуемым образом алгоритм обратного прохода по матрице V' (см. Align33). Если в последней строчке или последнем столбце матрицы V' имеется несколько элементов с максимальным значением, то использовать вариант оптимального выравнивания (A1, A2), в котором строка A1 содержит наибольшее число конечных пробелов, а при отсутствии вариантов с конечными пробелами для A1 — вариант, в котором наибольшее число конечных пробелов содержит строка A2. На следующих этапах построения оптимального выравнивания выбор варианта выполнять в соответствии с указаниями Align34. Вывести найденное выравнивание (A1, A2).
Align40°. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, и матрица оценок (структура матрицы описана в Align29). Кроме того, дана матрица V', полученная методом восходящей рекурсии (см. Align38). Найти все варианты оптимального выравнивания для S1 и S2 при условии бесплатных граничных пробелов, модифицировав требуемым образом алгоритм обратного прохода по матрице V' (см. Align33). Варианты оптимального выравнивания (A1, A2) перебирать следующим образом: при наличии вариантов с конечными пробелами в строке A1 перебирать их в порядке убывания количества этих пробелов; затем, при наличии вариантов с конечными пробелами в строке A2, перебирать их в порядке убывания этих пробелов; затем, при наличии варианта выравнивания с отсутствующими конечными пробелами, обрабатывать этот вариант. Перебор вариантов с совпадающим числом конечных пробелов выполнять в соответствии с указаниями Align35. Вывести все найденные оптимальные выравнивания.
Align41°. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, и матрица оценок (структура матрицы описана в Align29). Найти значение сходства и один из вариантов оптимального выравнивания для S1 и S2 при условии бесплатных граничных пробелов, используя метод восходящей рекурсии для построения матрицы V' (см. Align38) и выполняя обратный проход по матрице V' (см. Align39). Выбор варианта оптимального выравнивания выполнять в соответствии с указаниями Align39.
Align42°. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, и матрица оценок (структура матрицы описана в Align29). Найти значение сходства и все варианты оптимального выравнивания для S1 и S2 при условии бесплатных граничных пробелов, используя метод восходящей рекурсии для построения матрицы V' (см. Align38) и выполняя обратный проход по матрице V' (см. Align39). Перебор вариантов оптимального выравнивания выполнять в соответствии с указаниями Align40.
Align43°. Пропуском (англ. gap) называется любой последовательный ряд пробелов в строке выравнивания, ограниченный непробельными символами или началом/концом строки. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, числа ws (≥ 0) и wg (> 0) — вес пробела и пропуска соответственно, а также матрица оценок, аналогичная матрице, описанной в Align29, но содержащая только m строчек и m столбцов (в матрице отсутствуют строчка и столбец, соответствующие символу пробела, поскольку все оценки, связанные с пробелами считаются одинаковыми и равными −ws). Найти значение сходства для строк S1 и S2 (см. Align30) при дополнительном предположении, что каждый пропуск вносит в это значение «штраф», равный −wg (наряду со штрафами −ws, вносимыми каждым пробелом, входящим в пропуск). Если через W(i, j) обозначить сходство строк S1[1..i] и S2[1..j] при учете пропусков, то рекуррентные формулы для W(i, j) примут следующий вид (в данных формулах используются вспомогательные функции E(i, j) и F(i, j)): • W(0, 0) = 0;
• для любого i > 0 W(i, 0) = −wg − i·ws, E(i, 0) = −2·wg − i·ws;
• для любого j > 0 W(0, j) = −wg − j·ws, F(0, j) = −2·wg − j·ws;
• для i > 0 и j > 0 W(i, j) = max{E(i, j), F(i, j), W(i − 1, j − 1) + s(S1[i], S2[j])}, где E(i, j) = max{E(i, j − 1), W(i, j − 1) − wg} − ws, F(i, j) = max{F(i − 1, j), W(i − 1, j) − wg} − ws. Для эффективного нахождения значений W(i, j) использовать метод восходящей рекурсии, основанный на последовательном вычислении элементов вспомогательных матриц E, F и W (действия при заполнении матриц аналогичны действиям при заполнении матрицы D, описанным в Align5). Значение сходства строк S1 и S2 при учете пропусков будет равно W(|S1|, |S2|). Вывести найденное значение сходства для S1 и S2, а также элементы последней строчки матрицы E и последнего столбца матрицы F: En,j, j = 0, …, p, Fi,p, i = 0, …, n, где n = |S1|, p = |S2|. Примечание. Учет пропусков часто позволяет создавать выравнивания, которые лучше согласуются с анализируемыми (в частности, биологическими) моделями. Большее значение wg будет приводить к тому, что число пропусков в выравнивании уменьшится, и полученные в результате выравнивания строки распадутся на несколько «крупных» подстрок. Меньшие значения wg будут приводить к более фрагментированным выравниваниям. Вес отдельного пробела ws может полагаться равным 0, в этом случае при выравнивании будет учитываться только количество пропусков, но не их размер. Рассмотренный в задании вариант моделирования пропусков называется моделью с аффинным весом, так как вес одного пропуска длины q определяется аффинной функцией wg + q·ws.
Align44°. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, числа ws (≥ 0) и wg (> 0) — вес пробела и пропуска соответственно, а также матрица оценок (структура матрицы описана в Align43). Кроме того, дана матрица W, полученная методом восходящей рекурсии (см. Align43), и вспомогательные матрицы E и F (для матриц E и F элементы нулевых строк и столбцов не приводятся). Найти один из вариантов оптимального выравнивания для S1 и S2 при учете пропусков, используя следующий алгоритм обратного прохода по матрице W (ср. с Align33). Обратный проход по матрице W начинается с ее правого нижнего элемента и заканчивается левым верхним элементом. Для элементов W0,j перемещение всегда выполняется влево, для элементов Wi,0 — вверх. При i > 0 и j > 0 перемещение выполняется влево в случае Wi,j = Ei,j, вверх в случае Wi,j = Fi,j и по диагонали (влево и вверх) в случае Wi,j = Wi−1,j−1 + s(S1[i], S2[j]), причем перемещение по диагонали выполняется на одну позицию, перемещение влево — до элемента Wi,k (k < j), для которого выполняется соотношение Wi,k = Wi,j + wg + (j − k)·ws, а перемещение вверх — до элемента Wk,j (k < i), для которого выполняется соотношение Wk,j = Wi,j + wg + (i − k)·ws. Каждое перемещение влево на одну позицию соответствует вставке пробела в строку A1 и текущего элемента S2 в строку A2, каждое перемещение вправо на одну позицию — вставке пробела в строку A2 и текущего элемента S1 в строку A1. Перемещение по диагонали соответствует вставке в A1 и A2 текущих элементов S1 и S2 соответственно (символы в строках S1 и S2 перебираются с конца, строки A1 и A2 заполняются от конца к началу). При наличии нескольких вариантов оптимального выравнивания выбор варианта выполнять в соответствии с указаниями Align34. Вывести найденное выравнивание (A1, A2).
Align45°. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, числа ws (≥ 0) и wg (> 0) — вес пробела и пропуска соответственно, а также матрица оценок (структура матрицы описана в Align43). Кроме того, дана матрица W, полученная методом восходящей рекурсии (см. Align43), и вспомогательные матрицы E и F (для матриц E и F элементы нулевых строк и столбцов не приводятся). Найти все варианты оптимального выравнивания для S1 и S2 при учете пропусков, модифицировав требуемым образом алгоритм обратного прохода по матрице W (см. Align44). Перебор вариантов оптимального выравнивания выполнять в соответствии с указаниями Align35. Вывести все найденные оптимальные выравнивания.
Align46°. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, числа ws (≥ 0) и wg (> 0) — вес пробела и пропуска соответственно, а также матрица оценок (структура матрицы описана в Align43). Найти значение сходства и один из вариантов оптимального выравнивания для S1 и S2 при учете пропусков, используя метод восходящей рекурсии для построения матриц W, E и F (см. Align43) и выполняя обратный проход по матрице W (см. Align44). Выбор варианта оптимального выравнивания выполнять в соответствии с указаниями Align34.
Align47°. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, числа ws (≥ 0) и wg (> 0) — вес пробела и пропуска соответственно, а также матрица оценок (структура матрицы описана в Align43). Найти значение сходства и все варианты оптимального выравнивания для S1 и S2 при учете пропусков, используя метод восходящей рекурсии для построения матриц W, E и F (см. Align43) и выполняя обратный проход по матрице W (см. Align44). Перебор вариантов оптимального выравнивания выполнять в соответствии с указаниями Align35.
Align48°. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, числа ws (≥ 0) и wg (> 0) — вес пробела и пропуска соответственно, а также матрица оценок (структура матрицы описана в Align43). Найти значение сходства для строк S1 и S2 при учете пропусков (см. Align43) и дополнительном предположении, что все граничные пробелы (и связанные с ними пропуски) являются «бесплатными», т. е. имеют нулевой вес (см. Align38). Если через W'(i, j) обозначить сходство строк S1[1..i] и S2[1..j] в случае учета пропусков и бесплатных начальных пробелов, то рекуррентные формулы для W'(i, j) будут аналогичны формулам для W(i, j), приведенным в Align43; необходимо лишь изменить базовые условия, положив для любого i W'(i, 0) = 0 и для любого j W'(0, j) = 0 (базовые условия для функций E и F не изменятся, в рекуррентных формулах для вычисления значений E и F необходимо использовать значения W' вместо W). Для эффективного нахождения значений W'(i, j) следует использовать метод восходящей рекурсии, основанный на последовательном вычислении элементов вспомогательных матриц W', E и F (действия при заполнении матриц аналогичны действиям при заполнении матрицы D, описанным в Align5). Чтобы учесть условие бесплатности конечных пробелов, в качестве значения сходства для строк S1 и S2 следует выбрать наибольшее значение среди элементов матрицы W', расположенных в ее последней строчке или последнем столбце. Вывести найденное значение сходства для S1 и S2, а также элементы последней строчки и последнего столбца матрицы W': W'n,j, j = 0, …, p, W'i,p, i = 0, …, n, где n = |S1|, p = |S2|.
Align49°. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, числа ws (≥ 0) и wg (> 0) — вес пробела и пропуска соответственно, а также матрица оценок (структура матрицы описана в Align43). Кроме того, дана матрица W', полученная методом восходящей рекурсии (см. Align48), и вспомогательные матрицы E и F (для матриц E и F элементы нулевых строк и столбцов не приводятся). Найти один из вариантов оптимального выравнивания для S1 и S2 при бесплатных граничных пробелах и учете пропусков, модифицировав соответствующим образом алгоритм обратного прохода по матрице W' (см. Align44 и Align39). Выбор варианта оптимального выравнивания выполнять в соответствии с указаниями Align39. Вывести найденное выравнивание (A1, A2).
Align50°. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, числа ws (≥ 0) и wg (> 0) — вес пробела и пропуска соответственно, а также матрица оценок (структура матрицы описана в Align43). Кроме того, дана матрица W', полученная методом восходящей рекурсии (см. Align48), и вспомогательные матрицы E и F (для матриц E и F элементы нулевых строк и столбцов не приводятся). Найти все варианты оптимального выравнивания для S1 и S2 при бесплатных граничных пробелах и учете пропусков, модифицировав соответствующим образом алгоритм обратного прохода по матрице W' (см. Align44 и Align39). Перебор вариантов оптимального выравнивания выполнять в соответствии с указаниями Align40. Вывести все найденные оптимальные выравнивания.
Align51°. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, числа ws (≥ 0) и wg (> 0) — вес пробела и пропуска соответственно, а также матрица оценок (структура матрицы описана в Align43). Найти значение сходства и один из вариантов оптимального выравнивания для S1 и S2 при бесплатных граничных пробелах и учете пропусков, используя метод восходящей рекурсии для построения матриц W', E и F (см. Align48) и выполняя обратный проход по матрице W' (см. Align44 и Align39). Выбор варианта оптимального выравнивания выполнять в соответствии с указаниями Align39.
Align52°. Даны строки S1 и S2, число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, числа ws (≥ 0) и wg (> 0) — вес пробела и пропуска соответственно, а также матрица оценок (структура матрицы описана в Align43). Найти значение сходства и все варианты оптимального выравнивания для S1 и S2 при бесплатных граничных пробелах и учете пропусков, используя метод восходящей рекурсии для построения матриц W', E и F (см. Align48) и выполняя обратный проход по матрице W' (см. Align44 и Align39). Перебор вариантов оптимального выравнивания выполнять в соответствии с указаниями Align40.
Приближенные вхождения строк и локальное выравнивание
Align53°. Даны строки P, T (|P| < |T|) и число d (> 0) — точность приближения. Также дано число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, и матрица оценок (структура матрицы описана в Align29). Подстрока T' строки T называется приближенным вхождением P в T (с точностью d), если значение сходства P и T' (см. Align30) больше или равно d. Используя метод восходящей рекурсии (см. Align31), найти все подстроки строки T, которые имеют длину |P| и являются приближенными вхождениями P в T с точностью d. Вывести найденные приближенные вхождения; после каждого найденного вхождения выводить значение его сходства с P (вхождения перебирать по возрастанию позиции их начального символа). Вывести также количество найденных приближенных вхождений.
Align54°. Даны строки P, T (|P| < |T|) и число d (> 0) — точность приближения. Также дано число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, и матрица оценок (структура матрицы описана в Align29). Эффективный алгоритм нахождения конечных позиций всех приближенных вхождений P в T состоит в следующем (определение приближенного вхождения приведено в Align53): • с помощью метода восходящей рекурсии построить вспомогательную матрицу V (см. Align31) для строк P и T, изменив базовые условия: для любого j V0,j = 0 (условия для Vi,0 остаются прежними);
• позиция k строки T соответствует конечной позиции некоторого приближенного вхождения P в T с точностью d, если Vn,k ≥ d (n обозначает длину строки |P|). Используя описанный алгоритм, определить количество позиций строки T, соответствующих конечным позициям всех приближенных вхождений P в T, и вывести это количество, а также последнюю строчку матрицы V: Vn,j, j = 0, …, |T|.
Align55°. Даны строки P, T (|P| < |T|) и число d (> 0) — точность приближения. Также дано число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, матрица оценок (структура матрицы описана в Align29) и матрица V, полученная методом восходящей рекурсии (см. Align54). Для нахождения подстроки матрицы T, являющейся приближенным вхождением P с точностью d, достаточно выполнить обратный проход по матрице V по правилам, приведенным в Align33 (получаемые при этом вспомогательные строки A1 и A2 будут содержать соответствующее оптимальное выравнивание). Обратный проход начинается с какого-либо элемента последней строчки, значение которого больше или равно d: Vn,k ≥ d, где n = |P|. Заканчивается обратный проход на элементе расположенном в нулевой строчке V. Индекс j символа строки T, добавленного последним в выравнивание A2 при обратном проходе, определяет начальную позицию приближенного вхождения; таким образом, искомое приближенное вхождение равно подстроке T[j..k]. Используя описанный алгоритм, найти приближенное вхождение P в T с минимальной конечной позицией k (предполагается, что хотя бы одно приближенное вхождение существует). Если на некотором шаге обратного хода имеется несколько вариантов выбора очередного элемента, то предпочтительным является перемещение вверх, а при его невозможности — перемещение по диагонали. Вывести найденное приближенное вхождение T', его начальную позицию в строке T, а также значение сходства для строк P и T' и оптимальное выравнивание (A1, A2) для этих строк. Примечание. Приведенное условие выбора варианта очередного элемента матрицы V в алгоритме обратного хода обеспечивает построение одного из кратчайших приближенных вхождений P в T, заканчивающихся в позиции k.
Align56°. Даны строки P, T (|P| < |T|) и число d (> 0) — точность приближения. Также дано число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, матрица оценок (структура матрицы описана в Align29) и матрица V, полученная методом восходящей рекурсии (см. Align54). Для каждой позиции k строки T, в которой оканчивается приближенное вхождение P в T, найти одно из таких вхождений, выполняя обратный проход по матрице V (см. Align55). Если в позиции k оканчиваются несколько вариантов приближенных вхождений, то выбор варианта выполнять в соответствии с указаниями Align55. Для каждого найденного вхождения T' = T[j..k] вывести позиции j и k его начального и конечного символа в строке T, значение сходства для строк P и T' и оптимальное выравнивание (A1, A2) для этих строк. Вхождения перебирать по возрастанию позиции k их конечного символа. Вывести также количество найденных приближенных вхождений.
Align57°. Даны строки P, T (|P| < |T|) и число d (> 0) — точность приближения. Также дано число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, и матрица оценок (структура матрицы описана в Align29). Найти приближенное вхождение P в T с минимальной конечной позицией k, используя алгоритм восходящей рекурсии для построения матрицы V (см. Align54) и выполняя обратный проход по матрице V (см. Align55); предполагается, что хотя бы одно приближенное вхождение существует. Если в позиции k заканчиваются несколько вариантов приближенных вхождений, то выбор варианта выполнять в соответствии с указаниями Align55. Вывести найденное приближенное вхождение T', его начальную позицию в строке T, а также значение сходства для строк P и T' и оптимальное выравнивание (A1, A2) для этих строк.
Align58°. Даны строки P, T (|P| < |T|) и число d (> 0) — точность приближения. Также дано число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, и матрица оценок (структура матрицы описана в Align29). Для каждой позиции k строки T, в которой заканчивается приближенное вхождение P в T, найти одно из таких вхождений, используя алгоритм восходящей рекурсии для построения матрицы V (см. Align54) и выполняя обратный проход по матрице V (см. Align55). Если в позиции k заканчиваются несколько вариантов приближенных вхождений, то выбор варианта выполнять в соответствии с указаниями Align55. Для каждого найденного вхождения T' = T[j..k] вывести позиции j и k его начального и конечного символа в строке T, значение сходства для строк P и T' и оптимальное выравнивание (A1, A2) для этих строк. Вхождения перебирать по возрастанию позиции k их конечного символа. Вывести также количество найденных приближенных вхождений.
Align59°. Даны строки S1 и S2. Также дано число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, и матрица оценок (структура матрицы описана в Align29). Задача локального суффиксного выравнивания S1 и S2 для пары позиций (i, j) состоит в нахождении (возможно, пустых) суффиксов s1 и s2 строк S1[1..i] и S2[1..j] соответственно с максимальным значением сходства v(i, j) (максимум ищется по всем парам возможных суффиксов строк S1[1..i] и S2[1..j]). Дополнительно предполагается, что две пустые строки имеют сходство 0. Для нахождения v(i, j) можно использовать следующие соотношения: • для любого i v(i, 0) = 0;
• для любого j v(0, j) = 0;
• если i > 0 и j > 0, то v(i, j) = max{0, v(i − 1, j) + s(S1[i], _), v(i, j − 1) + s(_, S2[j]), v(i − 1, j − 1) + s(S1[i], S2[j])} (символ «_» в формуле обозначает пробел; следует обратить внимание на то, что максимум всегда будет неотрицательным). Эффективное нахождение значений v(i, j) выполняется методом восходящей рекурсии, основанным на последовательном вычислении элементов вспомогательной матрицы v (действия при заполнении матрицы v аналогичны действиям при заполнении матрицы D, описанным в Align5). Используя метод восходящей рекурсии, найти матрицу v и вывести элементы ее двух последних строчек: vn−1,j, j = 0, …, |S2|, vn,j, j = 0, …, |S2|, где n = |S1|.
Align60°. Даны строки S1 и S2 и числа i (≤ |S1|) и j (≤ |S2|). Также дано число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, матрица оценок (структура матрицы описана в Align29) и матрица v, полученная методом восходящей рекурсии (см. Align59). Решить задачу локального суффиксного выравнивания для данной пары позиций (i, j); для этого выполнить обратный проход по матрице v (по правилам, аналогичным приведенным в Align33), начиная с элемента vi,j и заканчивая элементом, равным 0 (получаемые при этом вспомогательные строки A1 и A2 будут содержать соответствующее оптимальное суффиксное выравнивание). Индекс i' символа строки S1, добавленного последним в выравнивание A1 при обратном проходе, и индекс j' символа строки S2, добавленного последним в выравнивание A2, будут определять начальные позиции суффиксов s1 и s2, обеспечивающих оптимальное суффиксное выравнивание: s1 = S1[i'..i], s2 = S2[j'..j] (при этом значение сходства будет равно vi,j). Если при обратном проходе в выравнивание A1 и/или A2 не будет добавлено ни одного символа, то соответствующий суффикс полагается равным пустой строке, а значение i' и/или j' — равным 0. Если на некотором шаге обратного хода имеется несколько вариантов выбора очередного элемента, то предпочтительным является перемещение вверх, а при его невозможности — перемещение по диагонали. Вывести найденные суффиксы s1 и s2, их начальные позиции i' и j' в строках S1 и S2 соответственно, а также значение сходства для строк s1 и s2 и оптимальное выравнивание (A1, A2) для этих строк. Некоторые из строк s1, s2, A1, A2 (а возможно, и все эти строки) могут быть пустыми.
Align61°. Даны строки S1 и S2. Также дано число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, матрица оценок (структура матрицы описана в Align29) и матрица v, полученная методом восходящей рекурсии (см. Align59). Задача локального выравнивания для строк S1 и S2 состоит в нахождении подстрок s1 и s2 строк S1 и S2 соответственно с максимальным значением сходства v* (максимум ищется по всем парам различных подстрок строк S1 и S2). Данная задача связана с задачей локального суффиксного выравнивания (см. Align59) следующим образом: v* = max{v(i, j)}, i ≤ |S1|, j ≤ |S2|, причем если максимум v(i, j) достигается на паре позиций (i*, j*), то пара подстрок, решающая задачу локального суффиксного выравнивания для (i*, j*), одновременно решает задачу локального выравнивания строк S1 и S2. Используя алгоритм обратного прохода для решения задачи суффиксного выравнивания (см. Align60), найти подстроки s1 и s2, решающие задачу локального выравнивания. Если имеется несколько пар позиций, на которых достигается максимум функции v, то выбрать пару с минимальным значением i*, а для пар с одинаковым минимальным значением i* — с минимальным значением j*. Если при выполнении обратного прохода из позиции (i*, j*) можно получить несколько вариантов подстрок s1 и s2, то выбор варианта выполнять в соответствии с указаниями Align60. Вывести значения v*, i*, j*, подстроки s1 и s2, а также оптимальное выравнивание (A1, A2) для этих подстрок.
Align62°. Даны строки S1 и S2. Также дано число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв, и матрица оценок (структура матрицы описана в Align29). Найти одну из пар подстрок (s1, s2), решающих задачу локального выравнивания, используя алгоритм восходящей рекурсии для построения матрицы v (см. Align59), учитывая связь матрицы v с задачей локального выравнивания (см. Align61) и выполняя обратный проход по матрице v (см. Align60). Если имеется несколько пар подстрок, решающих задачу локального выравнивания, то выбор пары выполнять в соответствии с указаниями Align61. Вывести максимальное значение сходства v*, позиции i*, j* начала подстрок s1 и s2, сами подстроки s1 и s2, а также оптимальное выравнивание (A1, A2) для этих подстрок.
Align63°. Даны строки S1 и S2. Найти длину наибольшей общей подстроки строк S1 и S2, сведя эту задачу к определению характеристики v* задачи локального выравнивания (см. Align61). Для этого значения матрицы оценок s определить следующим образом: s(x, y) = 1 при x = y и s(x, y) = −100 при x ≠ y (x, y — символы, входящие в строки S1 и S2, а также символ пробела). Для нахождения характеристики v* построить матрицу v, используя алгоритм восходящей рекурсии (см. Align59). Вывести найденное значение v*, номер k первой из строчек матрицы v, в которой содержится значение v*, и элементы строчки k матрицы v: vk,j, j = 0, …, |S2|.
Align64°. Даны строки S1 и S2, а также матрица v, полученная методом восходящей рекурсии (см. Align59) при использовании матрицы оценок s специального вида, описанной в Align63. Найти одну из общих подстрок строк S1 и S2 наибольшей длины, сведя эту задачу к определению пары подстрок (s1, s2), решающих задачу локального выравнивания (см. Align61). Для нахождения подстрок s1, s2 учесть связь матрицы v с задачей локального выравнивания (см. Align61) и выполнить обратный проход по матрице v (см. Align60). Если имеется несколько пар подстрок, решающих задачу локального выравнивания, то выбор пары выполнять в соответствии с указаниями Align61. Вывести подстроку s1 — общую подстроку строк S1 и S2 наибольшей длины (благодаря специальному выбору матрицы оценок эта подстрока будет совпадать с подстрокой s2), а также позиции i* и j*, начиная с которых подстрока s1 входит в строки S1 и S2 соответственно.
Align65°. Даны строки S1 и S2. Найти все общие подстроки строк S1 и S2 наибольшей длины, сведя эту задачу к определению пар подстрок (s1, s2), решающих задачу локального выравнивания при использовании матрицы оценок специального вида, описанной в Align63. Для нахождения подстрок s1 и s2 построить матрицу v, используя алгоритм восходящей рекурсии (см. Align59), учесть связь матрицы v с задачей локального выравнивания (см. Align61) и выполнить обратный проход по матрице v (см. Align60) для каждого элемента матрицы v с максимальным значением. Элементы vi,j с максимальным значением перебирать по возрастанию индекса i, а для равных индексов i — по возрастанию индекса j. Вывести каждую найденную общую подстроку наибольшей длины и позиции i* и j*, начиная с которых эта подстрока входит в строки S1 и S2 соответственно. Вывести также количество найденных общих подстрок.
Нахождение наибольшей общей подпоследовательности
Align66°. Даны строки P и T (|P| < |T|). Подпоследовательностью строки T называется строка, составленная из символов строки T, взятых в том порядке, в котором они входят в эту строку (символы, входящие в подпоследовательность, в отличие от символов подстрок, не обязаны располагаться подряд в исходной строке). Просматривая символы строк P и T не более одного раза, проверить, входит ли строка P в качестве подпоследовательности в строку T, и вывести True, если входит, и False в противном случае. Вывести также количество сравнений символов, которое потребовалось для решения задачи. В алгоритме учесть, что если еще не просмотренная часть строки T имеет размер, меньший еще не просмотренной части строки P, то строка P не может быть подпоследовательностью строки T.
Align67°. Даны строки S1 и S2. Общей подпоследовательностью строк S1 и S2 называется подпоследовательность, которая входит одновременно в S1 и S2. Задача о наибольшей общей подпоследовательности заключается в поиске самой длинной общей подпоследовательности (англ. longest common subsequence — LCS) строк S1 и S2. Длина LCS для двух строк совпадает со значением сходства этих строк (см. Align30), если матрица оценок определяется следующим образом: s(x, y) = 1 при x = y и s(x, y) = 0 при x ≠ y (x, y — символы, входящие в строки S1 и S2, а также символ пробела). Найти длину LCS для данных строк S1 и S2, используя алгоритм восходящей рекурсии для построения матрицы V (см. Align31). Вывести элементы двух последних строчек матрицы V: Vn−1,j, j = 0, …, |S2|, Vn,j, j = 0, …, |S2|, где n = |S1| (искомая длина LCS будет равна последнему элементу матрицы V).
Align68°. Даны строки S1 и S2, а также матрица V, полученная методом восходящей рекурсии (см. Align31) при использовании матрицы оценок специального вида, описанной в Align67. Найти одну из наибольших общих подпоследовательностей (LCS) строк S1 и S2, выполняя обратный проход по матрице V по правилам, приведенным в Align33. Строка, соответствующая LCS, заполняется справа налево; очередной символ добавляется к ней в случае, когда переход от элемента Vi,j выполняется по диагонали (к элементу Vi−1,j−1, имеющему значение, на 1 меньшее значения Vi,j); при этом к строке LCS добавляется символ S1[i] (равный символу S2[j]). Если на некотором шаге обратного хода имеется несколько вариантов выбора очередного элемента, то выбор предпочтительного варианта выполнять в соответствии с указаниями Align34. Вывести строку, соответствующую найденной LCS, и позиции i и j, с которых начинается найденная LCS в строках S1 и S2.
Align69°. Даны строки S1 и S2. Найти одну из наибольших общих подпоследовательностей (LCS) строк S1 и S2, используя алгоритм восходящей рекурсии для построения матрицы V (см. Align31) и выполняя обратный проход по матрице V (см. Align68). Если на некотором шаге обратного хода имеется несколько вариантов выбора очередного элемента, то выбор предпочтительного варианта выполнять в соответствии с указаниями Align34. Вывести строку, соответствующую найденной LCS, и позиции i и j, с которых начинается найденная LCS в строках S1 и S2.
Align70°. Дано число N (≤ 50) и набор A из N чисел. Подпоследовательностью набора A называется набор элементов из А, расположенных в том же порядке, в котором они входят в исходный набор A. Покрытием набора A называется совокупность невозрастающих подпоследовательностей A; при этом каждый элемент набора A входит в покрытие ровно один раз. Размером покрытия называется число входящих в него подпоследовательностей. Наименьшим покрытием называется покрытие наименьшего размера. Найти наименьшее покрытие A, используя следующий жадный алгоритм: • элементы A перебираются, начиная с первого, и каждый элемент помещается в конец первой невозрастающей подпоследовательности, которую он может продолжить (существующие подпоследовательности перебираются в порядке возрастания их номеров);
• если ни одну существующую подпоследовательность очередной элемент из A продолжить не может, то он начинает подпоследовательность с новым порядковым номером. Вывести размер полученного покрытия и все элементы каждой входящей в него подпоследовательности, перебирая подпоследовательности в порядке возрастания их номеров. Вывести также количество сравнений чисел из набора A, которое потребовалось для нахождения наименьшего покрытия. Примечание. Описанный алгоритм построения наименьшего покрытия имеет порядок O(N·K), где N — размер исходного набора, а K — размер наименьшего покрытия.
Align71°. Дано число N (≤ 50), число B и набор из N чисел Ai, i = 1, …, N. Числа Ai упорядочены по неубыванию. Определить позицию j в наборе A, в которую надо вставить число B с сохранением упорядоченности набора. Использовать для этого следующий вариант алгоритма бинарного поиска: (1) в набор A добавляются два «барьерных» элемента: A0, меньший min{A1, B} («минус бесконечность»), и AN+1, больший max{AN, B} («плюс бесконечность»);
(2) переменная i полагается равной 0, переменная j — равной N + 1;
(3) пока справедливо неравенство j − i ≠ 1, выполнять следующие действия: положить переменную k равной i + (j − i)/2 (символ «/» обозначает операцию деления нацело); если Ak ≥ B, то записать значение k в переменную j, иначе записать значение k в переменную i. После завершения алгоритма для найденной позиции j будет выполняться двойное неравенство (с учетом наличия барьерных элементов): Aj−1 < B ≤ Aj; таким образом, j будет определять требуемую позицию вставки элемента B. Вывести найденную позицию j и количество сравнений чисел Ak и B, выполненных в цикле (3), которое потребовалось для ее определения. Примечание. Алгоритм бинарного поиска имеет порядок O(log N), где N — размер исходного набора чисел. При вычислении значения k фактически берется среднее арифметическое для i и j, т. е. (i + j)/2 (с учетом целочисленного деления), однако использованная формула i + (j − i)/2 является более надежной, так как обеспечивает защиту от переполнения при больших значениях i и j.
Align72°. Дано число N (≤ 50) и набор A из N чисел. Найти наименьшее покрытие A, используя модификацию жадного алгоритма, описанного в Align70. В модифицированном жадном алгоритме учитывается следующее свойство подпоследовательностей, входящих в покрытие: в любой момент выполнения жадного алгоритма последние элементы существующих подпоследовательностей упорядочены по возрастанию. Поэтому для нахождения подпоследовательности с наименьшим номером, которую может продолжить очередной элемент из набора A, можно использовать алгоритм бинарного поиска, описанный в Align71. При реализации алгоритма бинарного поиска можно считать, что значения элементов из набора A лежат в диапазоне от 0 до 1000. Вывести размер полученного покрытия и все элементы каждой входящей в него подпоследовательности, перебирая подпоследовательности в порядке возрастания их номеров. Вывести также количество сравнений чисел из набора A, которое потребовалось для нахождения наименьшего покрытия. Примечание. Благодаря использованию алгоритма бинарного поиска модифицированный жадный алгоритм построения наименьшего покрытия имеет порядок O(N·log K), где K — размер наименьшего покрытия.
Align73°. Дано наименьшее покрытие некоторого набора чисел A (см. Align70): вначале указывается количество K входящих в него невозрастающих подпоследовательностей (K ≤ 15), затем для каждой подпоследовательности (в порядке возрастания их номеров) указывается число элементов подпоследовательности L (≤ 15) и сами элементы. Найти одну из наибольших возрастающих подпоследовательностей (англ. longest increasing sequence — LIS) исходного набора A, используя следующий алгоритм: • элементы LIS определяются с конца (в порядке убывания их номеров), число элементов равно K;
• в качестве последнего, K-го элемента LIS берется последний элемент последней, K-й подпоследовательности;
• затем перебираются остальные подпоследовательности (в порядке убывания их номеров), из каждой подпоследовательности выбирается первый из элементов, значение которых строго меньше элемента, ранее добавленного в LIS, и этот элемент добавляется к LIS перед ранее добавленным элементом. Вывести элементы построенной наибольшей возрастающей подпоследовательности, а также количество сравнений чисел из набора A, которое потребовалось для нахождения LIS. Примечание. Описанный алгоритм построения LIS по наименьшему покрытию имеет порядок O(N), где N — общее число элементов в исходном наборе, так как в ходе этого алгоритма каждый элемент набора анализируется не более одного раза.
Align74°. Дано число N (≤ 50) и набор A из N чисел. Используя модифицированный жадный алгоритм построения наименьшего покрытия A (см. Align72) и алгоритм нахождения наибольшей возрастающей подпоследовательности набора A по его наименьшему покрытию (см. Align73), найти одну из наибольших возрастающих подпоследовательностей (LIS) набора A. Вывести размер LIS, ее элементы, а также количество сравнений чисел из набора A, которое потребовалось для нахождения LIS. Примечание. Полный алгоритм построения LIS, включающий предварительное построение наименьшего покрытия, имеет порядок O(N·log K), где N — число элементов в исходном наборе, а K — длина LIS (равная размеру наименьшего покрытия).
Align75°. Даны строки S1, S2 (|S2| ≤ |S1| < 20) и число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв. Построить по данным строкам набор чисел, используя следующий алгоритм: • для каждого символа x, встречающегося в S1, создается список тех позиций, в которых символ x встречается в S2, причем позиции в этом списке перебираются по убыванию;
• в результирующий набор чисел помещаются созданные списки в порядке, соответствующем порядку следования в строке S1 связанных с этими списками символов (один и тот же список может быть добавлен в набор несколько раз, если соответствующий этому списку символ несколько раз входит в строку S1). С помощью подходящих структур данных (например, вспомогательных одномерного и двумерного массива) обеспечить построение всех списков позиций за один просмотр строки S2. Чтобы избежать многократного дублирования полученных списков, удобно хранить результирующий набор в виде массива ссылок на созданные списки. Вывести размер полученного набора чисел и его элементы.
Align76°. Даны строки S1 и S2, число N (≤ 50) и набор A из N чисел, построенный по строкам S1 и S2 в соответствии с алгоритмом, описанным в Align75. Данный набор обладает следующим свойством: любая возрастающая подпоследовательность набора A определяет некоторую общую подпоследовательность строк S1 и S2 той же длины, причем для получения общей подпоследовательности символов достаточно взять символы строки S2, расположенные в позициях, равных значениям элементов числовой подпоследовательности. Поэтому любая наибольшая возрастающая подпоследовательность (LIS) набора A определяет некоторую наибольшую общую подпоследовательность (LCS) строк S1 и S2. Используя модифицированный жадный алгоритм построения наименьшего покрытия набора A (см. Align72) и алгоритм нахождения наибольшей возрастающей подпоследовательности A по наименьшему покрытию (см. Align73), найти одну из LIS набора A и вывести соответствующую ей LCS для строк S1 и S2 в виде строки символов. Вывести также количество сравнений чисел из набора A, которое потребовалось для нахождения LIS.
Align77°. Даны строки S1 и S2 (|S2| ≤ |S1| < 20) и число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв. Построить по данным строкам набор чисел A, описанный в Align75, и, используя модифицированный жадный алгоритм построения наименьшего покрытия A (см. Align72) и алгоритм нахождения наибольшей возрастающей подпоследовательности (LIS) набора A по наименьшему покрытию (см. Align73), найти одну из LIS набора A и вывести соответствующую ей наибольшую общую подпоследовательность (LCS) для строк S1 и S2 (см. Align76) в виде строки символов. Вывести также количество сравнений чисел из набора A, которое потребовалось для нахождения LIS.
Align78°. Даны строки S1, S2 и S3 (|S3| ≤ |S2| ≤ |S1| < 20) и число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв. Построить по данным строкам набор пар чисел, используя следующий алгоритм: • для каждого символа x, встречающегося в S1, создается список пар (i, j), в которых элемент i соответствует позиции вхождения символа x в S2, а элемент j — позиции вхождения этого же символа в S3; пары содержат все возможные комбинации позиций вхождения и располагаются по лексикографическому убыванию: (x1, x2) > (y1, y2), если либо x1 > y1, либо x1 = y1 и x2 > y2;
• в результирующий набор пар чисел помещаются созданные списки в порядке, соответствующем порядку следования в строке S1 связанных с этими списками символов (один и тот же список может быть добавлен в набор несколько раз, если соответствующий этому списку символ несколько раз входит в строку S1). Используя вспомогательные структуры данных (например, два вспомогательных одномерных и двумерных массива) для хранения позиций, связанных со строками S2 и S3 по отдельности, обеспечить построение требуемого набора за один просмотр строк S2 и S3. Вывести размер полученного набора и его элементы — пары чисел.
Align79°. Даны строки S1, S2 и S3 (|S3| ≤ |S2| ≤ |S1| < 20), число N (≤ 70) и набор A из N пар чисел, построенный по строкам S1, S2 и S3 в соответствии с алгоритмом, описанным в Align78. Значение пары чисел X = (x1, x2) считается строго меньшим значения пары Y = (y1, y2) (обозначение X < Y), если одновременно выполняются два строгих неравенства: x1 < y1 и x2 < y2. Возрастающей подпоследовательностью набора A считается подпоследовательность пар, в которой любой элемент подпоследовательности строго меньше последующего элемента. Набор A обладает следующим свойством: любая его возрастающая (в указанном выше смысле) подпоследовательность определяет некоторую общую подпоследовательность строк S1, S2 и S3 той же длины (для получения общей подпоследовательности символов достаточно взять символы строки S2, расположенные в позициях, равных значениям первых элементов пар подпоследовательности набора A). Поэтому любая наибольшая возрастающая подпоследовательность (LIS) набора A определяет некоторую наибольшую общую подпоследовательность (LCS) строк S1, S2 и S3. Для нахождения LIS в данном случае можно использовать следующий алгоритм: • наряду с набором A числовых пар ввести в рассмотрение наборы чисел P и B того же размера N;
• значение P1 положить равным 1, значение B1 — равным 0;
• значение Pi, i = 2, …, N, положить равным max{Pj} + 1, где в качестве j берутся номера в диапазоне от 1 до i − 1, для которых выполняется неравенство Aj < Ai, а значение Bi положить равным минимальному из тех номеров j, для которых достигается максимум Pj (если ни одного такого номера не найдено, то Pi положить равным 1, а Bi — равным 0);
• найти K — длину LIS, равную maxi=1,…,N{Pi};
• для нахождения одной из LIS применить обратный ход: в качестве последнего элемента LIS выбирается первый из элементов Aq, для которых Pq = K; если элемент LIS с номером i уже определен (и равен элементу Aj), то в качестве предыдущего элемента LIS (с номером i − 1) берется элемент набора A с номером Bj. Используя данный алгоритм, найти одну из LIS набора A и вывести соответствующую ей LCS для строк S1, S2 и S3 в виде строки символов. Примечание. Описанный в задании алгоритм нахождения LIS имеет порядок O(N2). Применить более быстрый алгоритм (порядка O(N·log K)), основанный на построении минимального покрытия и бинарном поиске (см. Align73), мешает то обстоятельство, что в наборе пар A могут содержаться несравнимые пары X и Y, для которых не выполняется ни одно из соотношений X < Y, X = Y, Y < X (например, (1, 2) и (2, 1)).
Align80°. Даны строки S1, S2 и S3 (|S3| ≤ |S2| ≤ |S1| < 20) и число m (< 10) — размер алфавита, состоящего из первых строчных латинских букв. Построить по данным строкам набор A пар чисел, описанный в Align78, после чего, действуя по схеме, описанной в Align79, найти одну из наибольших возрастающих подпоследовательностей (LIS) набора A и вывести соответствующую ей наибольшую общую подпоследовательность (LCS) для строк S1, S2 и S3 в виде строки символов.
|
