Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Сравнение СУБД Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3   вперед  Ctrl      все
 Re: СУБД для хранения генома.  [new]
tip78
Member

Откуда: Москва
Сообщений: 1266
а, вот эта часть:
автор
- в геноме должна быть возможность поиска определённой последовательности по 40-60% совпадений (искомая последовательность до
2000 бит) и по точному совпадению более коротких последовательность (искомая последовательность до 50 бит). А так же сравнение
двух последовательностей.

ну так в hex упаковать, да и всё
16 июн 18, 00:21    [21495601]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
mayton
Member

Откуда: loopback
Сообщений: 52917
tip78
mayton, вы утверждаете, что первые 20-40 нуклеотидов не будут уникальными?

Я ничего не говорил про уникальнлсть.
16 июн 18, 08:43    [21495770]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709
softwarer
rigor mortis,

задача как она описана вообще не особо для БД, имхо. По сути нужен список blob-ов и какой-то хитрый индекс по нему. Реализовывать этот индекс на 99.99% всё равно придётся самостоятельно, а в остальном функциональность БД просто не требуется.


Именно.
Да и вообще подход так себе, проектировать тут серьезную базу на форуме, в чате.
Этим надо профессионально заниматься.
16 июн 18, 09:02    [21495782]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709
Парень набросил и слился, а вы тут пыжитесь...
16 июн 18, 09:09    [21495789]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
mayton
Member

Откуда: loopback
Сообщений: 52917
Мортис. Ну что там? Как дела?
19 июн 18, 21:48    [21504577]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
hck1
Member [заблокирован]

Откуда:
Сообщений: 139
https://habr.com/company/microsoft/blog/344060/
24 июн 18, 23:08    [21517361]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
rigor mortis
Member

Откуда:
Сообщений: 82
mayton

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


Для вас открытие что существуют системы счисления, отличные от двоичных?
26 июн 18, 11:31    [21521311]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
mayton
Member

Откуда: loopback
Сообщений: 52917
rigor mortis
mayton
Четверичных бит? Вы слышали нечто подобное? И я задаю вам дальше вопрос. Мы будем оперировать символами?
Или битами? Битами какими? В нашем общепринятом понимании или в том в котором мыслит топик-стартер.


Для вас открытие что существуют системы счисления, отличные от двоичных?

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

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

Даю руку на отсечение что мы запутаемся в противном случае.
26 июн 18, 11:39    [21521368]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
Leonid Kudryavtsev
Member

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


Для вас открытие что существуют системы счисления, отличные от двоичных?

Мне кажется компактность хранения в этой задаче - дело 100500.
Первичны алгоритмы, а их то и нет.

Ну и бы побоялся на начальной стадии разработки, закладываться "впритык". Вдруг еще что-то хранить потребуется, что в 2 бита не влезет.
+

например из Вики:
Википедия_РНК
Всего в РНК насчитывается около 100 разных видов модифицированных нуклеотидов


Википедия_ДНК
В виде исключения, например, у бактериофага PBS1, в ДНК встречается пятый тип оснований — урацил ([U]), пиримидиновое основание, отличающееся от тимина отсутствием метильной группы на кольце, обычно заменяющее тимин в РНК[17].

26 июн 18, 11:52    [21521423]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
mayton
Member

Откуда: loopback
Сообщений: 52917
По поводу алгоритмов.

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

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

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

// Мышь саблезубая.
string s1 = "ACTGACTGAAAACCCCTTTGGG......"; 

// Ищем в этой мыши 3 цитозина подряд. 
string s2 = "CCC"; 



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

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

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

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

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

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

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

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

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

Базы данных

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

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

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

- Все данные Read/Only.
- Идеально паралеллятся для машин с раздельной памятью.(Много процессов на одной машине - скорее всего плохо т.к. просядет канал памяти.)
- Удобно запускать в Hadoop/Spark, возможно ApacheStorm (надо подумать).
26 июн 18, 12:35    [21521612]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
Никанор Кузьмич
Member

Откуда: Село Малые Кулики
Сообщений: 687
mayton
Никаких лексем и токенов нет.
Эээ, немножко есть. 3 основания (кодон) кодируют одну аминокислоту. Плюс есть специальный кодон, означающий "конец строки гена". Кстати, аминокислот порядка 20, а вариантов кодонов - 64 (помню только на школьном уровне, там небось как обычно 100500 нюансов у разных организмов), то есть разные куски ДНК могут кодировать идентичные белки. В поиске наверняка понадобится искать что-нибудь вроде "все гены, кодирующие такую-то аминокислотную последовательность".
26 июн 18, 13:11    [21521773]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
mayton
Member

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


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

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

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

1) Сколько всего аминокислот? Сколько брать букв алвавита?
2) Какова типичная длина генома для данной задачи. (В начале прозвучало что-то до 3 миллионов символов.)
3) Что надо искать? "все гены, кодирующие такую-то аминокислотную последовательность". Здесь-бы нужен
пример. Какой длины эта последовательность (в среднем).
4) Будем искать много и часто в одном геноме? Или одноразово во многих? Это ключевой момент в алгоримах и индексах.
5) Зачем нечеткий поиск? Что это? Как выглядит результат нечеткого матчинга? Как близко мы должны
быть в этой нечеткости? 50% ? 80% ?
6) Визуальный аппарат. Как вы (биологи) видите данные? Вряд-ли 3 миллона символов вам информативны.
Возможно есть какой-то стандарт на отображение. Спектр там.... Цветные матрицы. Или какой-то усредненный
грубый набор символов.
26 июн 18, 13:33    [21521848]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54751

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

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

Posted via ActualForum NNTP Server 1.5

26 июн 18, 14:03    [21521967]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
mayton
Member

Откуда: loopback
Сообщений: 52917
Dimitry Sibiryakov
mayton
5) Зачем нечеткий поиск? Что это? Как выглядит результат нечеткого матчинга? Как близко мы
должны быть в этой нечеткости? 50% ? 80% ?

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

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

AAA(C)CDDDDE -> AAACDDDDE


Это будет та-же близость что и в первом варианте? Или вообще не близко?
26 июн 18, 14:48    [21522236]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
Jan Kowalski-Smith
Member

Откуда:
Сообщений: 29
Может Genomics?
https://azure.microsoft.com/en-us/services/genomics/
27 июн 18, 00:39    [21523868]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
skyANA
Member

Откуда: Зеленоград
Сообщений: 28355
rigor mortis,

Genomics England uses MongoDB to Power the Data Science Behind the 100,000 Genomes Project
7 июл 18, 14:18    [21551964]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
Lepsik
Member

Откуда: glubinka
Сообщений: 4257
наберите отдельную таблицу с цепочками по 32 аминокислоты.
само днк будет набиратся из ссылок на эту таблицу.

Дальше поиск будет заметно быстрее
14 авг 18, 23:19    [21642442]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
Eugene New
Member

Откуда:
Сообщений: 456
делайте это максимально плохо, чтобы ни у кого не возникло возможности этим пользоваться. вы же тоже человек.
29 сен 18, 21:06    [21690067]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
старый пень
Member

Откуда: из леса
Сообщений: 24
Ваще в БД генома структурированная инфа тоже должна быть, типа классификация организма, область, экзон/ интрон, название гена, если это конкретный ген а не кусок хромосомы, инфа о конкретном носителе (имя фамилия) и тд и тп. Дофига, я помни полей 15 было.

И ваще много вариаций. В РНК есть U, у разных зверей разные аминокислоты, по уму это всё в БД тоже запихивать надо.

насчет ридонди... вдруг автор сам гены читает?

Главное, зачем что-то изобретать? Давно есть готовые решения. Уже лет 20 назад, когда эти БД распростанялись на лазерных дисках, были описаны форматы хранения, предоставлялись библиотеки для доступа, КМК ковыряться с большими СУБД в этом деле смысла вообще нет.
30 сен 18, 09:36    [21690243]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
ну я
Member

Откуда: Москва
Сообщений: 1276
rigor mortis
- в геноме должна быть возможность поиска определённой последовательности по 40-60% совпадений (искомая последовательность до
2000 бит)

Неточное совпадение - это с удалением или с заменой вхождения? И каких длин и на какие?
1 окт 18, 17:06    [21691596]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
ну я
Member

Откуда: Москва
Сообщений: 1276

// Мышь саблезубая.
string s1 = "ACTGACTGAAAACCCCTTTGGG......";

// Ищем в этой мыши 3 цитозина подряд.
string s2 = "CCC";

Индексируем позиции одного символа, двух символов, трех символов, и т.д., сколько не жалко.


^GI("Mouse sable","A")=1
^GI("Mouse sable","A")=5
^GI("Mouse sable","A")=6
...
^GI("Mouse sable","AC")=1
^GI("Mouse sable","AC")=5
^GI("Mouse sable","AC")=12
...

После чего запрашиваем позиции где есть "C" после которого идет "C", после которого идет ....
И найти такую последовательность этих позиций, расстояние между которыми меньше чем... ну и в нужном порядке следования.
Как на sql сделать - не знаю, а на М это но проблем, там любые индексы можно сделать.
1 окт 18, 17:52    [21691658]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
старый пень
Member

Откуда: из леса
Сообщений: 24
ну я,

с индексами КМК не сильно катит.

Предположим, есть последовательность из 2000 знаков, где первые 500 почти не совпадают, зато дальше почти совпадают так, что общий критерий 40% выполняется влегкую. Боюсь представить, сколько будет знанимать индекс на все возможные слова длиной 500 символов, и, главное, он все равно не поможет.
5 окт 18, 10:45    [21696085]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
ну я
Member

Откуда: Москва
Сообщений: 1276
старый пень
ну я,

с индексами КМК не сильно катит.

Предположим, есть последовательность из 2000 знаков, где первые 500 почти не совпадают, зато дальше почти совпадают так, что общий критерий 40% выполняется влегкую. Боюсь представить, сколько будет знанимать индекс на все возможные слова длиной 500 символов, и, главное, он все равно не поможет.

На всевозможные не нужно, нужно на сколько не жалко. Последовательность в 500 элементов проверяется как 100 последовательностей в 5 элементов.

"и, главное, он все равно не поможет" - давненько я не встречал таких сильных аргументаций ))))
Хотя у женщин попадался еще более сильный - "бе-бе-бе"
5 окт 18, 11:58    [21696190]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
старый пень
Member

Откуда: из леса
Сообщений: 24
ну я
Последовательность в 500 элементов проверяется как 100 последовательностей в 5 элементов.

Забавный бред. А если совпадающий кусок начинатется с 99 позиции? Достаточно рамку на 1 букву сдвинуть и надо всё искать заново. В том то и дело, что если надо достичь предела точности в 40%, то, что б воспользоваться индексом, всё равно придется сравнивать начиная со ВСЕХ позиций из начала сравнимаего куска длиной почти 40%.

Даже для слов по 100 нуклеотидов, с учетом того, что последовательности могут быть совершенно произвольными, сколько вариатов ожидется, 4^100 , если не ошибаюсь?

Это очень нетривиальные задачи, а не словарь русского языка длиной всего в 20000 слов, где длина слова редко превосходит 16 букв. Я в прошлой жизни занимался поиском экзонов, используя марковсие цепи, там стартовые якоря были длиной всего в 3 нуклеотида, и все равно неделями шуршало, что б статистику набрать (правда на 486м).
5 окт 18, 12:47    [21696280]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для хранения генома.  [new]
S.G.
Member

Откуда: cartoon network
Сообщений: 30611
ну я
Последовательность в 500 элементов проверяется как 100 последовательностей в 5 элементов.

сильно.
9 окт 18, 13:50    [21699254]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3   вперед  Ctrl      все
Все форумы / Сравнение СУБД Ответить