старый пеньА если совпадающий кусок начинатется с 99 позиции? Достаточно рамку на 1 букву сдвинуть и надо всё искать заново. В том то и дело, что если надо достичь предела точности в 40%, то, что б воспользоваться индексом, всё равно придется сравнивать начиная со ВСЕХ позиций из начала сравнимаего куска длиной почти 40%.
Сравниваемый кусок имеет несколько символов (пусть для определенности будет N) в начале? Имеет. По ним можем по индексу взять где они начинаются в индексированной последовательности? Можем. После этих N символов есть еще N других символов? Есть. они должны отстоять от полученных по первым N на N позиций. Можем из первого индекса пропустить те котором это условие не удовлетворяет? Можем. Ну и так далее.

ТАК НАХРЕНА БРАТЬ ВСЕ ПОЗИЦИИ, ЕСЛИ ЕСТЬ ИНДЕКС ПО ПОДСТРОКАМ, ИТИТЬ КОЛОТИТЬ?

maytonну яКак на sql сделать - не знаю, а на М это но проблем, там любые индексы можно сделать.
Мне кажется твоя М-система попрехнется объемом индекса. И еще до того
как получить решение мы получим "unable to extent segment" или как оно там называется.

Если я не прав - то приведи мне пожалуйста хотя-бы приблизительные расчеты размера этого
индекса исходя из базовой постановки (3 миллиона нуклеотидов и 2000 искомых символов).
"unable to extent segment" или как оно там называется - это в Oracle называется.

Не поперхнется. Ни моя, ни какая другая промышленная. С чего? Это не SQL, где помирают от объема.
Цепочка в 3 миллиона нуклеотидов при индексации по N символов в подстроке это 3 миллиона минус эти N записей в индексе на одну ДНК.
Даже для моей реализации М несколько миллионов - это просто штатные тесты на быстродействие,
чтобы работало достаточно долго для засекания времени. Из-за компрессии индексов там на диске может и гига не будет.
Для современных СУБД и дисков это как-бы вообще не объемы, чтобы париться.

Вот если будет миллионы не нуклеотидов в одной ДНК, а миллионы самих ДНК, тут диски могут понадобиться.

Меня же больше интересует, что так тормозит топикстартер с формализацией процента совпадений.
Пока нет постановки что (у него) это такое, толком можно обсуждать лишь строгий поиск, а нестрогий - ну в силу неполноты информации тут можно что угодно в любой момент прикрутить под рубрикой "а мне не подходит".

kealon(Ruslan)ну яНе поперхнется. Ни моя, ни какая другая промышленная. С чего? Это не SQL, где помирают от объема.
Цепочка в 3 миллиона нуклеотидов при индексации по N символов в подстроке это 3 миллиона минус эти N записей в индексе на одну ДНК.какой алгоритм используется для реализации индекса?
B*