ostapbender
@ostapbender

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

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

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

DBCA,
AC
ACB
BCA

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

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

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

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

Может быть, коллективный разум что-нибудь может предложить? Ограничений по памяти и алгоритмической сложности нет — последовательности от силы в 4 элемента каждая, общее их число — не больше 10.
  • Вопрос задан
  • 3927 просмотров
Пригласить эксперта
Ответы на вопрос 2
Arktos
@Arktos
Для алгоритма для 2 мы имеем 2 указателя (или индекса) — где мы находимся на первой строке и где на второй. Здесь же будем хранить n (или 10) указателей и делать тоже самое (то есть перебирать выбираемый символ и смещать указатели при совпадении). Понятно, что массивом это делать неудобно как для случая из 2 строк, поэтому я бы завел струкуру, хранящую указатели, и поместил бы ответы не в массив, а в map. Если непонятно, могу быстро написать код — это несложно (C++ или Java)
Ответ написан
Комментировать
@vilgeforce
Раздолбай и программист
Погуглите «multiple sequence alignment»
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы