tip78mayton, вы утверждаете, что первые 20-40 нуклеотидов не будут уникальными?
Я ничего не говорил про уникальнлсть.

Мортис. Ну что там? Как дела?

rigor mortismaytonЧетверичных бит? Вы слышали нечто подобное? И я задаю вам дальше вопрос. Мы будем оперировать символами?
Или битами? Битами какими? В нашем общепринятом понимании или в том в котором мыслит топик-стартер.


Для вас открытие что существуют системы счисления, отличные от двоичных?
Вообще ни разу не открытие. Я изучал телеграфию и передачу данных техникуме.
Я вообще - связист по 1-му образованию.

Но в данном конкретном топике во избежание путаницы и mangling, я настаиваю
на том чтобы мы использовали термин бит в нашем смысле в котором его пишут
в 99% случаев в форумах. А данный enum = { A, C, T, G } c аденином и прочими
символами мы рассматривали отдельно как особый тип данных.

Даю руку на отсечение что мы запутаемся в противном случае.

По поводу алгоритмов.

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

Что есть у нас?

Длинный кусок говна вида





Никаких лексем и токенов нет. Разделителей нет. Стемминга нет. Нет никаких
предположений относительно жанра текста. Что подать на вход текстовому
движку? Непонятно. Не за что зацепиться.

И что надо найти? Факт наличия? Факт наличия + 1 совпадение? Или все вышесказанное
+ вектор совпадений.

Пускай автор скажет что.

Индексирование.

Как? Очевидно что для единоразового поиска это гиблое дело. Индексировать
имеет смысл строку s1 в том случае когда у нас есть понимание того
как ускорить КМП или БМ на основе знаний об s2 (или там будет не s2 а
целое множество подстрок).

Еще вариант. Мы можем имея 1000 геномов саблезубых мышей проиндексировать
наличие факта какого-то под-геномчика и таким образом ускорить поиск. Признаки
положить рядом с мышью в виде хеш-тегов или карты блума. Но здесь я влезаю
в опасную зону прогнозов относительно задачи которую я еще не понимаю.
Надо - ли индексировать много мышей? Будут ли повторные поиски? Это
должен автор мне сказать. Все не хочу больше глядеть в хрустальный шар.

Нечеткий поиск.

Как? Здесь индекс еще менее вероятен.

Можно эдакий Код Хэмминга для скользящих трех цитозинов по геному мыши
и в тех местах где у нас есть 100% совпадение мы проставим в вещественный
вектор 1.0. А там где совпало 2 цитозина а третий символ не совпал будет
соотв 0.66666666. И таких вещественных векторов надо построить по количеству
искомых под-геномчиков s2. Пускай автор скажет это оно или не оно.

Базы данных

Я долго думал. Скорее нет. Не подходят. В тех БД что я знаю нет никаких механизмов
для оптимизации решения данной задачи. Тут главный смысл - алгоритм поиска подстроки
(возможно нечеткого) и способность задачи очень быстро себя распараллелить по вычислительным
узлам (не 4-8 как в кластере БД) а хотя бы в узлов 100 - 1000. Вобщем как в этих ваших амазонах.

Использовать БД просто как сторедж для данной задачи - скорее ДА. Можно. Но это будет
такой-себе юзкейс. Не лучше чем файловая система. Тразнакции не нужны.

Но есть и хорошие поинты.

- Все данные Read/Only.
- Идеально паралеллятся для машин с раздельной памятью.(Много процессов на одной машине - скорее всего плохо т.к. просядет канал памяти.)
- Удобно запускать в Hadoop/Spark, возможно ApacheStorm (надо подумать).

Никанор КузьмичmaytonНикаких лексем и токенов нет.Эээ, немножко есть. 3 основания (кодон) кодируют одну аминокислоту. Плюс есть специальный кодон, означающий "конец строки гена". Кстати, аминокислот порядка 20, а вариантов кодонов - 64 (помню только на школьном уровне, там небось как обычно 100500 нюансов у разных организмов), то есть разные куски ДНК могут кодировать идентичные белки. В поиске наверняка понадобится искать что-нибудь вроде "все гены, кодирующие такую-то аминокислотную последовательность".

Кузьмич. Это всё безумно интересно! Кодоны всякие там шмодоны.
Но постановка усложняется а мы никуда не двинулись.
Каждая ваша фраза требует расшифровки с примерами.

Нам не нужна идеальна и общая постановка. Мы с ней никуда не уедем. Или сменим работу и пойдем в биологи.
Нам нужно средненькое причёсанное It-шное ТЗ в терминах нам понятных. Строки. Поиск. Хранилище. Отчет. И требования по времени. Ну там... больше года ждать никто не будет. Ну и интерфейс. Как оно вообще должно выглядеть с точки
зрения юзера.

Пожалуйста ответьте на следующее.

1) Сколько всего аминокислот? Сколько брать букв алвавита?
2) Какова типичная длина генома для данной задачи. (В начале прозвучало что-то до 3 миллионов символов.)
3) Что надо искать? "все гены, кодирующие такую-то аминокислотную последовательность". Здесь-бы нужен
пример. Какой длины эта последовательность (в среднем).
4) Будем искать много и часто в одном геноме? Или одноразово во многих? Это ключевой момент в алгоримах и индексах.
5) Зачем нечеткий поиск? Что это? Как выглядит результат нечеткого матчинга? Как близко мы должны
быть в этой нечеткости? 50% ? 80% ?
6) Визуальный аппарат. Как вы (биологи) видите данные? Вряд-ли 3 миллона символов вам информативны.
Возможно есть какой-то стандарт на отображение. Спектр там.... Цветные матрицы. Или какой-то усредненный
грубый набор символов.

Dimitry Sibiryakovmayton5) Зачем нечеткий поиск? Что это? Как выглядит результат нечеткого матчинга? Как близко мы
должны быть в этой нечеткости? 50% ? 80% ?

Чтобы искать похожие геномы. И выводить релевантность.
То есть в базе есть "AAACCDDDDE", и оно должно найтись на поиск "AABCCDDEDE".
Я так это понимаю.

Левенштейн катит? Ну тоесть если я взял 1 аминокислоту удалил.




Это будет та-же близость что и в первом варианте? Или вообще не близко?