Алгоритм выравнивания последовательностей

Question

[ostapbender]

Мое почтение!

Есть четыре последовательности символов:

DBCA,
AC
ACB
BCA

Необходимо трансформировать эти последовательности в (примерно) следующие:

D-BCA-
-A-C--
-A-C-B
--BCA-

То есть, «выровнять» эти последовательности таким образом, чтобы на среди всех последовательностей в каждой позиции было максимальное число идентичных элементов (словами коряво; из примера, надеюсь, понятнее).

Википедия на Sequence Alignment предлагает некоторое число алгоритмов, но работают они с двумя последовательностями, тогда как мне надо выравнивать больше и как их расширить для обработки N последовательностей — не придумаю.

Может быть, коллективный разум что-нибудь может предложить? Ограничений по памяти и алгоритмической сложности нет — последовательности от силы в 4 элемента каждая, общее их число — не больше 10.

Answer 1

[Arktos]

Для алгоритма для 2 мы имеем 2 указателя (или индекса) — где мы находимся на первой строке и где на второй. Здесь же будем хранить n (или 10) указателей и делать тоже самое (то есть перебирать выбираемый символ и смещать указатели при совпадении). Понятно, что массивом это делать неудобно как для случая из 2 строк, поэтому я бы завел струкуру, хранящую указатели, и поместил бы ответы не в массив, а в map. Если непонятно, могу быстро написать код — это несложно (C++ или Java)

Answer 2

[Владимир Мартьянов]

Погуглите «multiple sequence alignment»