Рекордные сравнения ДНК ускоряют криминалистику
Криминалисты используют ДНК-профили из базы данных ФБР (NDIS, 18 млн профилей) для поиска подозреваемых или родственников через анализ родства. Однако обработка сложных образцов (с ДНК нескольких людей) и масштабирование — вычислительная проблема. Например, при 100 000 образцов в неделю для сравнения с 18 млн профилей.
Исследователи создали веб-платформу IdPrism с двумя алгоритмами — FastID и TachysSTR, — которые кодируют генетические маркеры (STR и SNP) в биты (0 или 1). Это позволяет:
- Идентифицировать более 10 человек в сложной смеси ДНК.
- Проводить расширенный анализ родства.
Как работают алгоритмы:
Используются три аппаратные битовые инструкции:
- Исключающее ИЛИ (XOR): сравнивает два профиля. Результат 0 — совпадение маркера, 1 — несовпадение.
- Логическое И (AND): устраняет "шум" несовпадений от других людей в смешанном образце.
- Подсчет населения (popcount): суммирует все единицы. Много 0 — совпадение, много 1 — несовпадение.
Производительность:
- FastID: сравнивает 5000 SNP в образце с 20 млн эталонных профилей менее чем за 12 секунд (альтернативные методы — часы).
- TachysSTR: сравнивает STR в 1 млн образцов за 1,8 секунды (текущие алгоритмы — 10 минут).
Точность повышена за счёт панели из 2650 SNP-маркеров для анализа сложных образцов и родства.
Система IdPrism, отмеченная наградой R&D 100 Award 2018 года, перешла к внешним пользователям в ноябре 2018 года.