| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Определение прототипа последовательности |
| Автор: Fally 25.10.2008, 18:32 | ||
| Здравствуте. Сейчас столкнулся с проблемой, и не знаю с какой стороны к ней подойти... К примеру, у меня есть исходная последовательность "абвгд", и есть набор след. последовательностей: "ааабббвввгггддд", "аабввггдед", "дададабаба", "ккллммнноо".... и мне необходимо определить прототипом каких последовательностей является исходна... В данном случае, первая последовательность удовлетворяет нашим требованиям, поскольку там все символы повторяются равное число раз, вторая тоже подходит под прототипируемую, несмотря на наличие шума в виде некоторых ошибок, исходная последовательность не является прототипом третьей последовательности, но в то же время является прототипом четвёртой последовательности. Мощность алфавита строго задана и не может превышать 15 символов, при этом каждый "соседние символы" могут заменять друг друга и считаются похожими. Также может подойти последовательность со схожей структурой, например 4ая.. Наверное условие поставлено ужасно, поэтому изображу наглядно ^__^:
Очень хотелось бы, чтобы кто-нибудь подсказал направление куда мне копать и что считать. Заранее спасибо. |
| Автор: DRUID3 25.10.2008, 19:26 |
| хм... а на каком языке предстоит решить это? И еще не понял о 4-й последовательности... Она то чем похожа??? |
| Автор: Fally 27.10.2008, 15:52 |
| DRUID3, Язык будет С++.. А обоснование похожести последовательности #4 в том, что символы хоть и отличаются от исходной но находятся в таком же расстоянии, что и символы исходной, а также количество их повторов кратно количеству аналогичных символов в исходной... т.е. приблизительная цепочка такова: "абвг" == "бвгд" == "ввггддее" != "апде". Имеет роль количество повторов, и расстояние между символами.. и + к условию тот факт, что порядок символов в алфавите жёстко задан... |
| Автор: nworm 28.10.2008, 02:40 |
| 1) получаем однобуквенные последовательности, из которых могла произойти проверяемая последовательность 2) находим расстояния между первой буквой и второй, второй и третьей и т.д. Если все расстояния совпадают всё ок. Пример ккллммнноо 1)клмно 2) 1 1 1 1 1 совпадает с ааббввггдд 1)абвгд 2) 1 1 1 1 1 ---------------------------------------------------------------------------------------------------------------------------------- Иногда, если требуется определять на сколько одно сочетаний букв похоже на другое, вводят метрику (аналог расстояния между этими сочетаниями букв). |
| Автор: Fally 28.10.2008, 10:50 |
| nworm, спасибо большое за подсказку, а Вы случайно не знаете, какую литературу можно почитать прямо или косвенно связанную с эффективной обработкой больших последовательностей, т.к. я только для примера сделал такие короткие, а реально они будут минимум шестьсот-семьсот элементов? |
| Автор: nworm 28.10.2008, 23:18 |
| Надо знать Вашу предметную область. У одних и тех же последовательностей может быть совершенно разный смысл. Например, можете что-нибудь почитать про поиск в Интернете http://www.i2r.ru/static/334/out_6055.shtml По ссылке про любые тексты, так что можете что-то придумывать для своего случая. Если у Вас биология, то можно смотреть другие источники Тут поисковик какие-то нуклеотидные последовательности выдал: http://www.impb.ru/index.php?lang=rus&id=div/lkm/lunina_proj3 |
| Автор: Fally 29.10.2008, 12:47 |
| Спасибо большое за информацию. |