Здравствуте. Сейчас столкнулся с проблемой, и не знаю с какой стороны к ней подойти...
К примеру, у меня есть исходная последовательность "абвгд", и есть набор след. последовательностей: "ааабббвввгггддд", "аабввггдед", "дададабаба", "ккллммнноо".... и мне необходимо определить прототипом каких последовательностей является исходна... В данном случае, первая последовательность удовлетворяет нашим требованиям, поскольку там все символы повторяются равное число раз, вторая тоже подходит под прототипируемую, несмотря на наличие шума в виде некоторых ошибок, исходная последовательность не является прототипом третьей последовательности, но в то же время является прототипом четвёртой последовательности. Мощность алфавита строго задана и не может превышать 15 символов, при этом каждый "соседние символы" могут заменять друг друга и считаются похожими. Также может подойти последовательность со схожей структурой, например 4ая..
Наверное условие поставлено ужасно, поэтому изображу наглядно ^__^:

Очень хотелось бы, чтобы кто-нибудь подсказал направление куда мне копать и что считать.
Заранее спасибо.

хм... а на каком языке предстоит решить это? И еще не понял о 4-й последовательности... Она то чем похожа???  

DRUID3, Язык будет С++.. А обоснование похожести последовательности #4 в том, что символы хоть и отличаются от исходной но находятся в таком же расстоянии, что и символы исходной, а также количество их повторов кратно количеству аналогичных символов в исходной... т.е. приблизительная цепочка такова: "абвг" == "бвгд" == "ввггддее" != "апде". Имеет роль количество повторов, и расстояние между символами..

 и + к условию тот факт, что порядок символов в алфавите жёстко задан...

1) получаем однобуквенные последовательности, из которых могла произойти проверяемая последовательность
2) находим расстояния между первой буквой и второй, второй и третьей и т.д.

Если все расстояния совпадают всё ок.

Пример
ккллммнноо
1)клмно
2) 1 1 1 1 1

совпадает с ааббввггдд
1)абвгд
2) 1 1 1 1 1

----------------------------------------------------------------------------------------------------------------------------------

Иногда, если требуется определять на сколько одно сочетаний букв похоже на другое, вводят метрику 
(аналог расстояния между этими сочетаниями букв).

nworm, спасибо большое за подсказку, а Вы случайно не знаете, какую литературу можно почитать прямо или косвенно связанную с эффективной обработкой больших последовательностей, т.к. я только для примера сделал такие короткие, а реально они будут минимум шестьсот-семьсот элементов?

Надо знать Вашу предметную область. У одних и тех же последовательностей может быть совершенно разный смысл.

Например, можете что-нибудь почитать про поиск в Интернете
http://www.i2r.ru/static/334/out_6055.shtml
По ссылке про любые тексты, так что можете что-то придумывать для своего случая.

Если у Вас биология, то можно смотреть другие источники
Тут поисковик какие-то нуклеотидные последовательности выдал:
http://www.impb.ru/index.php?lang=rus&...km/lunina_proj3



Это сообщение отредактировал(а) nworm - 28.10.2008, 23:19

Спасибо большое за информацию.