Давайте пока забъем болт на возможную экономию.
И представим геном текстовой строкой из алфавита 4х букв.

Просто нам так будет проще с терминологией.

Автор пишет


Переводя на наш язык. БД должна хранить строки от 500 символов до 3 мега-символов.

Здесь особо нечего выбирать. Здесь нужно key-value хранилище.

Типа

keyvalueСаблезубая мышь.genomATGCATGCATGCATGCATGC.....Комар писклявый кусачий.genomAAAAAGGGGGTTTTTCCCCCC....
Согласен с softwarer по поводу акцента на алгоритмах. По большему счету здесь даже СУБД особо не нужна.
Нужен эффективный алгоритм индексирования. Учитывая специфику - это не текстовый поиск. Могу чуть
позже аргументировать почему. Но сперава задам вопросы Ригор-Мортису.

По поводу специализированных СУБД для генетики. Здесь я не готов ничего комментировать.
Но скорее всего их сила не в хранении а в обработке. Тоесть в алгоритмах сопоставления нечетких ключей.
И я вангую что подобных проектов очень мало и они стоят денег.

А мы можем уйти от биологии и плавно подойти к.. Терминологии которая общепринята в it?

982183,

Как энтузиаст и бывший радио-любитель я готов поддержать тему аналоговой техники. Но мне кажется будет разумным обсуждать здесь постановку в терминах it и в русле Сравнения СУБД.

Рнк-днк и и прочаа биологическая атрибутика - В форум биологов. Аналоговая техника - тоже оффтоп.

Поверьте старому модератору.

Leonid Kudryavtsevбудем обсуждать чем битики и байтики в БД MySQL отличаются от битиков и байтиков в PostgreSQL ? :-)

А я объясню. Я считаю что это очень важно. На самом старте ТЗ договорится о терминологии.

Автор пишет.


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

Далее. По поводу строк и целых чисел. Другой господин в топике пишет


Отвечу сразу. Никакого смысла. Вообще никакого. Можно искать пользу в экономии места. Но не забывайте
что нам надо двигать шаблон по геному и искать совпадения или частичные совпадения. Как вы их будете искать?
Двигать биты в четверичных целых? Хм... Ну я-б подумал. Для 3 200 000 нуклеотидов мы получим 3-х мегабайтную
строку в классическом представлении + аппарат строковых операций. Или мы можем децл сэкономить и получить
в 4 раза меньше тоесть 3 200 000 / 4 = 800 000 или 800 килобайт упакованных бит. И кучу головняка с тем
как это матчить. Не забывайте что нам надо двигать информацию кратно позиции нуклеотида а не байта.
Вобщем думайте.

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 аминокислоту удалил.




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

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

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