Локальное происхождение как задача оптимизации: несовпадения + λ · переключения
Dias-Alves, Mairal, Blum. Loter: A Software Package to Infer Local Ancestry for a Wide Range of Species. Mol Biol Evol 35(9):2318–2326, 2018
Максим Кирилюк · 19 ноября 2026
Задача
LAI — раскрасить хромосому по происхождению
гаплотип смешанной особи, SNP 1 … p
■ популяция A ■ популяция B
Вход: фазированный гаплотип h смешанной особи и референсные панели K популяций.
Выход: для каждого SNP j — метка происхождения aj ∈ {1, …, K}.
Это одномерная сегментация: метка на каждой позиции, и метки идут длинными кусками.
Постановка: Dias-Alves et al. 2018, «New Approaches»
Почему куски
Длина тракта — это часы
Каждое поколение рекомбинация режет хромосому. В модели симуляций статьи длина куска в Морганах ~ Exp(μ), μ — поколений после смешения: среднее 1/μ M = 100/μ cM.
поколений после смешения μ =
Чем старше смешение, тем короче куски — и тем труднее их увидеть. Отсюда вся дальнейшая математика.
Simulations: «length (measured in Morgans) of an ancestry chunk is drawn according to an exponential distribution of rate μ». Соседние одноцветные куски сливаются в один тракт.
Что нужно на входе
Loter почти ничего не просит
HAPMIX
LAMP-LD
RFMix
Loter
Фазированные гаплотипы смешанных
нет
нет
да
да
Число предковых популяций
2
2, 3, 5
≥ 2
≥ 2
Генетическая карта (cM)
да
нет (физ. позиции)
да
нет (только порядок SNP)
Лимит числа SNP
нет
50 000
нет
нет
Коррекция ошибок фазирования
нет
не нужна
да
да, при K = 2
RFMix ещё просит число поколений и размер окна. У Loter — один параметр λ, и даже его в итоге усредняют.
Table 1 и раздел о параметрах RFMix, Dias-Alves et al. 2018
Модель копирования
Гаплотип — мозаика из референсных гаплотипов
Панель: 2n фазированных гаплотипов H1 … H2n, Hij ∈ {0, 1}; каждый принадлежит одной из K популяций.
Путь s = (s1, …, sp) ∈ {1, …, 2n}p: sj = k — на SNP j цель копирует Hk.
Происхождение: aj = популяция гаплотипа Hsj.
Идея копирования — Li & Stephens (2003), как в HAPMIX. Но без вероятностей.
Пример рис. 2: s = (5,5,5,5,1,1,1,1,2,2,2), одно несовпадение (×), два переключения → цена 1 + 2λ.
Eq. (1) и Fig. 2, Dias-Alves et al. 2018
Задача оптимизации · eq. (1)
Одна функция стоимости
Потеря — число SNP, где цель не совпала с копируемым гаплотипом.
Регуляризация — λ × число переключений донора. Большой λ → длинные куски.
Ищем ŝ = argmin C(s) по всем путям; ответ aj = pop(ŝj).
Переключение A1 → A2 стоит λ, но происхождение не меняет: смена донора ≠ граница тракта.
Eq. (1), Dias-Alves et al. 2018
Масштаб
Перебрать пути нельзя
Например, 2n = 200 референсных гаплотипов и p = 500 000 SNP: 200500 000 ≈ 101 150 515 путей.
Но стоимость складывается из локальных слагаемых: несовпадение зависит от одного SNP, штраф — от соседней пары. Значит, лучший путь до SNP j можно достраивать по одному шагу.
p = 500 000 — размер Populus-набора в сравнении скорости; 500 000 · log₁₀200 ≈ 1 150 515 — наш расчёт. Eq. (2)–(3), Dias-Alves et al. 2018
Граф · рис. 3
Лучший путь — кратчайший путь в слоистом графе
Вершина (i, j): «на SNP j копируем Hi», вес = |hj − Hij|.
Ребро по строке — 0, ребро в другую строку — λ.
Цена пути слева направо = C(s).
Это алгоритм Витерби, где вместо −log вероятностей — стоимости.
Fig. 3, Dias-Alves et al. 2018. Числа в вершинах — первые 5 SNP учебного примера со следующих слайдов; сравнение с Витерби — наша формулировка.
Динамическое программирование · eq. (4)
Рекуррентность и трюк с минимумом
Q(i, j) — цена лучшего пути по SNP 1..j, который на SNP j стоит в строке i; Q(i, 1) = |h1 − Hi1|.
Прыгать выгодно только с лучшей строки → mj−1 считаем один раз на столбец, клетка — O(1).
Итог: O(2n · p) на целевой гаплотип. Ответ — mini Q(i, p), путь — обратным проходом по указателям.
Память: Q нужен по одному столбцу, но указатели — вся таблица 2n × p.
Eq. (4); в статье опечатка i′ ∈ {1..n} — гаплотипов 2n (сверено с кодом graph.cpp:156–163). Сложность в статье записана как O(n × p) — тот же порядок.
Живой пример
Заполняем Q по столбцам, потом идём назад
λ = пришли прыжком
Учебный пример тьютора (thr_grjdfumr6b): 4 гаплотипа × 10 SNP; совпадает с loter_dp.py. Клавиши: S — шаг вперёд, A — назад.
Что делает λ
Шум и короткий тракт — для λ одно и то же
Внутри A-фона кусок, где цель совпадает с B на d информативных SNP. Два варианта: остаться в A — заплатить d несовпадений; уйти в B и вернуться — 2λ.
вставка B выгоднее ⇔ d > 2λнаш вывод из eq. (1), одиночная вставка
λ = сетка Loter: 1.5 … 5
d — (несовпадений с A) − (несовпадений с B) внутри куска. Это сравнение двух путей, не общий порог: в общем случае ΔC = −d + λ·ΔS (у края хромосомы ΔS = 1, порог d > λ; близкие вставки DP может объединить). Виджет — настоящий DP на A = 0…0, B = 1…1.
Правило в генетических единицах
Решает плотность SNP
При λ ∈ [1.5, 5] вставке B внутри постоянного A нужно больше 3 … 10 (то есть ≥ 4 … 11) чистых информативных SNP. Средний SNP-шаг: человек 2.7·10⁻³ cM (≈ 370 SNP/cM), Populus 9.8·10⁻⁶ cM (≈ 100 000 SNP/cM).
μ = SNP в среднем куске 100/μ cM, лог-шкала
Статья: LAI возможен и для смешения сотни поколений назад, «when SNP density is large enough, as for Populus data».
SNP-шаги — Discussion, Dias-Alves et al. 2018; перевод в SNP/cM и в SNP на кусок — наш расчёт.
Как не выбирать λ
Ансамбль: 8 значений λ × 20 бутстрепов
λ = 1 + 0.5 i, i = 1..8 1.5, 2, …, 5
×
20 бутстрепов референсы каждой популяции — выборка с возвращением
→
160 решений голосование большинством на каждом SNP
Если у победителя меньше 75% голосов — происхождение берётся у соседних SNP (в коде CLI порог другой).
Supp. Fig. S2: усреднение по λ лучше любого одного λ; бэггинг улучшает ещё. Лучший одиночный λ: 2 при μ = 400–500, иначе 5.
Мысль: λ «сложно зависит» от мутаций и рекомбинации — поэтому его не подбирают, а усредняют.
«New Approaches» и Discussion, Dias-Alves et al. 2018; бутстреп по референсам — код local_ancestry.py (bcm-uga/Loter @ 5c91354).
Ошибки фазирования · eq. (5)
Второе DP перераскладывает тракты между гаплотипами
Только при K = 2. Складываем два гаплоидных ответа в диплоидный dj ∈ {0, 1, 2}. Затем ищем две новые цепочки меток s, s′ (вспомогательные a, a′ ∈ {0,1}p, a + a′ = d) с минимумом
sw — число переключений меток; A1 = (0,…,0), A2 = (1,…,1). Ответ — xj = Asjj, yj = As′jj. Исключив a, a′, потеря на SNP равна |dj − xj − yj|: DP торгует расхождением с d против переключений, x + y = d не гарантировано наш вывод. O(p) на особь.
Проверка: 30% ошибок переключения фазы (CEU–YRI, 5 поколений) → та же диплоидная точность 97%, что с истинными фазами.
Eq. (5) и «Accounting for Phase Errors», Dias-Alves et al. 2018 (во втором слагаемом в тексте статьи индекс sj; по смыслу s′j).
Результаты · медианная диплоидная точность
Loter почти не стареет вместе со смешением
○ μ = 5 поколений● μ = 500 поколений
Человек: при μ ≤ 20 RFMix и LAMP-LD лучше; при μ ≥ 150 лучший — Loter.
Populus: Loter и LAMP-LD не зависят от возраста смешения; RFMix 92.0 → 65.3%.
Figs. 4–5 и раздел о времени работы, Dias-Alves et al. 2018
Длины трактов
Точность по SNP — не вся правда
медиана длины тракта, cM
истина
RFMix
Loter
LAMP-LD
Populus, 10 поколений
4.26
5.20
2.31
0.05
Человек, 10 поколений
9.03
9.99
12.20
9.02
Populus, 500 поколений
0.17
1.60
0.33
0.17
Loter и LAMP-LD дают ложные короткие куски и режут длинные тракты на части (Populus, 10 поколений).
RFMix при ≥ 200 поколениях восстанавливает тракты слишком длинными.
Fig. 6 и Supp. Fig. S6, Dias-Alves et al. 2018
Применение
Часы в деле: тополя
36 гибридов P. trichocarpa × P. balsamifera: в среднем 87% и 13% происхождения.
Медиана тракта balsamifera — 0.76 cM (квартили 0.25 и 1.47 cM).
Симуляции на реальных генотипах с μ ∈ {10, 50, 100, 200, 300, 500}: ближе всего распределение при μ = 100.
Вывод статьи: смешение было ≈ 100 поколений назад
«Application of Loter to Admixed Populus Individuals» и Fig. 7, Dias-Alves et al. 2018
Ограничения
Где модель упрощает
Слепота к расстояниям. Переключение стоит λ, будь между SNP 1 п.н. или 1 Мб (в коде есть необязательные веса, по умолчанию выключены).
Короткие тракты теряются: в сравнении A→B→A с постоянным A вставка с перевесом < 2λ информативных SNP невыгодна (на пороге — ничья); на плотных данных бывают ложные короткие куски.
Нужны фазированные данные и для цели, и для референсов.