Semargl.me: он-лайн сервис для анализа данных по Y-ДНК

[Semargl]

Все будеть номально - завтра сделаю возможность выборок из базы, по вашим условиям.
Те будет возможен запрос: "показать все DYS388 = 10 и DYS666 = 23"

Это было бы здорово... Так как текущая кластеризация многих гаплогрупп строится не только на открытых снипах, но и на предполагаемых по филогении и характерным значениям STR-маркеров. А для этих целей такая выборка была бы очень полезна.

С небольшой задержкой
Просьба оценить "запросы к БД". Интерфейс не сложный, разобраться легко.

Ошибки указанные ув. Оводом - исправил. Какие еще недостатки, в этой функции, вы замечаете? Или можно переходить к написанию другого функционала?

Приветствуется помощь в написании краткой инструкции пользователя для этой функции.
Хотелось бы видеть на языках: английском, немецком, русском, польском, финском.
"Поможите кто чем может"

Просьба остается в силе

[Semargl]

Начал писать, нечто подобное, функции поиска матчей в YSearch.
Затык на алгоритмах Левенштейна, и Хэмминга
Решил реализовать с помощью k-dimensional tree.
Нужен совет наших уважаемых математиков, правилен ли выбор алгоритма для нахождения подобных последовательностей строк? Естес-но приветствуется минимализация расхода вычислительных ресурсов.

Пока вышло сыровато, но прогресс есть
Заценить можно из меню поиска
Когда нашли нужный гаплотип, справа увидим ссылочку "Demo!!!", жмем, и получаем 100 самых близких, к заданному, гаплотипа.
Осталась одна проблемка, отсутствующий, в сравниваемом гаплотипе, маркер, дефолтно считается _совпавшим_, поэтому в самые близкие матчи вылазят короткие гаплотипы. Что с этим делать, подумаю чуток после, сейчас голова лопается )))

ПС Кому лень искать гаплотипы через поиск - прямая ссылка на матчи для 211347-Kotwicki

[Valery]

отсутствующий, в сравниваемом гаплотипе, маркер, дефолтно считается _совпавшим_, поэтому в самые близкие матчи вылазят короткие гаплотипы

Нормально. Кстати а как отсутствующие признаки у Вас реализуются в k-d?

[Semargl]

отсутствующий, в сравниваемом гаплотипе, маркер, дефолтно считается _совпавшим_, поэтому в самые близкие матчи вылазят короткие гаплотипы

Нормально. Кстати а как отсутствующие признаки у Вас реализуются в k-d?

Стыдно сказать
_пока_ реализуются, таким образом:
при отсутствии нужного признака, вместо него подставляется признак из гаплотипа, который взят для сравнения.
Это решило проблему больших дистанций между родственными гаплотипами, при отсутствии у одного из них нескольких значений маркёров. Но возникла более мелкая проблема (с короткими гаплотипами), которую все равно придется решить.
Думаю сделать сортировку по кол-ву сравниваемых маркёров: 111/67, 111/37, 111/12 и тд. То есть убрать "в хвост" все хороткие гаплотипы.

А как вообще можно реализовать отсутствующие признаки в k-d? Я думаю никак.

[Valery]

Ну скажем указывать среднее значение по локусу. Наверное так. Либо держать сразу несколько деревьев - по 12, 17, 37, 67 и 111

При этом могут быть гаплотипы у которых нет всего 1-2 локусов либо их значения явно ошибочны. Такие можно либо заменить средними либо восстановить филогенетически. Для 67 последнее возможно легко а вот если локусов мало то наверное можно только среднее пихать.

[Semargl]

Ну скажем указывать среднее значение по локусу. Наверное так. Либо держать сразу несколько деревьев - по 12, 17, 37, 67 и 111

При этом могут быть гаплотипы у которых нет всего 1-2 локусов либо их значения явно ошибочны. Такие можно либо заменить средними либо восстановить филогенетически. Для 67 последнее возможно легко а вот если локусов мало то наверное можно только среднее пихать.

Нагрузка возрастет в разы =)

Такие можно либо заменить средними либо восстановить филогенетически

Это будет уже из области догадок)
Я думаю "выбросить" все короткие гаплотипы, то есть в сравнении будут принимать участи только 67м и 111м
Хотя может посмотрю в сторону других алгоритмов, уж больно красив алгоритм вычисления расстояния Левенштейна. Но боюсь за ресурсы.
Хотя, именно этот алгоритм, применяется в биоинформатике для сравнения генов, хромосом и белков.

[Valery]

Это будет уже из области догадок)

так юзеру Вы отдадите данные как есть с "?", используя восстановленные значения только для поиска. Хотя согласен, что это все равно верный путь запутаться во лжи 

[Semargl]

Думаю сделать сортировку по кол-ву сравниваемых маркёров. То есть убрать "в хвост" все хороткие гаплотипы.

Немного подправил, уже красивше
Добавил, для отличающихся маркёров, маркировку цветом. Чем больше шаг, тем темнее цвет.

[Semargl]

Изменил алгоритм поиска ближайших гаплотипов. Раньше, алгоритм считал, что 10 шаговая мутация на 9 маркерах, более близкая, чем 11 шаговая, но на пяти маркерах.
Решил заново реализовать таблицу галотипов, входящих в бранч, но уже с автоматическим определением минимального, модального и максимального значения каждого маркера. Отличие от модала, в ту или иную сторону, будет отличаться по цвету.
Оценить можно со страницы списка бранчей, выбрав напротив нужного, ссылку: "Таблица гаплотипов in color"
Прямая ссылка на таблицу по "Сарматам".
ПС Просьба, пока не публиковать эти ссылки у "зарубежников". Фича пока сырая, и требует значительной доработки.
ППС Как всегда, отзывы и оценки, приветствуются.

[Овод]

Изменил алгоритм поиска ближайших гаплотипов. Раньше, алгоритм считал, что 10 шаговая мутация на 9 маркерах, более близкая, чем 11 шаговая, но на пяти маркерах.

Это очень тонкий вопрос. Существует три критерия генетической дистанции: помаркерный, поаллельный и квадратичный (в котором разницы в аллелях возводятся квадрат).
 
Первый работает лучше всего на слабо мутированных гаплотипах: понятно, что если, скажем, на 67 маркерах мы видим разницу только в одном маркере, но на 3 аллелях, то это, скорее всего, одна многошаговая мутация.
 
Второй - на средних дистанциях (примерно до различия в 20 маркерах из 67). Обычно на таких дистанциях линейность сохраняется ещё хорошо.
 
И, наконец, на сильно мутированных (свыше трети маркеров) уже имеет смысл оценивать возраст квадратичным методом. Хотя дисперсия оценки при этом будет зашкаливать. Линейный метод в этом случае даст более стабильную, но сильно смещенную в минус оценку возраста.
 
Так что проводить сортировну по среднему (второму) методу вполне целесообразно. Но при интерпретации стоит учитывать вышесказанное.

[NMT]

мысль Неспеца, а может результат выдавать сразу в трех варинтах (3 разные "кнопки" с указанием методов), люди сравнят, метод сходимости при разных вариантах обработки данных рулит, а вообще +еще один, четвертый результат как "сложение" этих 3 разных методов...
а?

[Semargl]

Изменил алгоритм поиска ближайших гаплотипов. Раньше, алгоритм считал, что 10 шаговая мутация на 9 маркерах, более близкая, чем 11 шаговая, но на пяти маркерах.

Это очень тонкий вопрос. Существует три критерия генетической дистанции: помаркерный, поаллельный и квадратичный (в котором разницы в аллелях возводятся квадрат).
 
Первый работает лучше всего на слабо мутированных гаплотипах: понятно, что если, скажем, на 67 маркерах мы видим разницу только в одном маркере, но на 3 аллелях, то это, скорее всего, одна многошаговая мутация.
 
Второй - на средних дистанциях (примерно до различия в 20 маркерах из 67). Обычно на таких дистанциях линейность сохраняется ещё хорошо.
 
И, наконец, на сильно мутированных (свыше трети маркеров) уже имеет смысл оценивать возраст квадратичным методом. Хотя дисперсия оценки при этом будет зашкаливать. Линейный метод в этом случае даст более стабильную, но сильно смещенную в минус оценку возраста.
 
Так что проводить сортировну по среднему (второму) методу вполне целесообразно. Но при интерпретации стоит учитывать вышесказанное.

Спасибо за совет. Прошу оценить оба варианта поиска. Как и прежде, на странице поиска, находим нужный гаплотип. Рядом с ним две ссылки: "демо1" и "демо2". Как Вы считаете, какой из примененных мной алгоритмов более подходит. Какой следует оставить?
Очень хорошо видно разницу на коротких гаплотипах: например для CP4ZB - Marchukov
Вариант1 и вариант2

а может результат выдавать сразу в трех варинтах

Уже. Но только как временное решение.

ПС Были "кривые" ссылки. Исправил.

[Овод]

Можно оставить оба варианта. Если же выбирать, то лучше стандартный (поаллельный).

[Lesla]

Владимир у тебя в базе:
201495 Matveev R1a-Prussian L366+
Прусская у нас вроде L365+

[Овод]

Вячеслав, там 2 разные "прусские" ветки: L365 и L366. Филогенетически они довольно сильно разнятся (хотя обе под Z280), но географически - близки.
 
Можно, конечно, L366 дать другое название, скажем "померанская". Но тагда будет полный контрапункт с поляками, которые называют L365 "померанской", а L366 - "прусской".
 
Хотя оба эти названия характеризуют, по большом счёту, один географический регион.