← → слайды · N заметки · T тема · F полный экран

НИС АДНЖ · метод локального происхождения

Loter
Локальное происхождение как задача оптимизации:
несовпадения + λ · переключения

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 почти ничего не просит

HAPMIXLAMP-LDRFMixLoter
Фазированные гаплотипы смешанныхнетнетдада
Число предковых популяций22, 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)

Одна функция стоимости

C(s)= ∑j=1p |hj−Hsj,j| +λ ∑j=1p−1 1sj≠sj+1

Потеря — число SNP, где цель не совпала с копируемым гаплотипом.

Регуляризация — λ × число переключений донора. Большой λ → длинные куски.

  • Ищем ŝ = argmin C(s) по всем путям; ответ aj = pop(ŝj).
  • Переключение A1 → A2 стоит λ, но происхождение не меняет: смена донора ≠ граница тракта.
Eq. (1), Dias-Alves et al. 2018

Масштаб

Перебрать пути нельзя

|{1,…,2n}p|=(2n)p

Например, 2n = 200 референсных гаплотипов и p = 500 000 SNP: 200500 000 ≈ 101 150 515 путей.

Но стоимость складывается из локальных слагаемых: несовпадение зависит от одного SNP, штраф — от соседней пары. Значит, лучший путь до SNP j можно достраивать по одному шагу.

Если sp = sp−1: C(s1..p) = C(s1..p−1) + |hp − Hspp|   (eq. 2)
Если sp ≠ sp−1: C(s1..p) = C(s1..p−1) + |hp − Hspp| + λ   (eq. 3)

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)= |hj−Hij|+ min(Q(i,j−1), mj−1+λ) mj−1= mini′Q(i′,j−1)
  • 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) с минимумом

C′= ∑j=1p|aj−Asjj|+ ∑j=1p|aj′−Asj′j|+ λ·sw(s)+λ·sw(s′)
  • 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%.
  • Скорость: 500 000 SNP, 20 тополей, 12 ядер — Loter 6 мин, RFMix 28, LAMP-LD 58.
Figs. 4–5 и раздел о времени работы, Dias-Alves et al. 2018

Длины трактов

Точность по SNP — не вся правда

медиана длины тракта, cMистинаRFMixLoterLAMP-LD
Populus, 10 поколений4.265.202.310.05
Человек, 10 поколений9.039.9912.209.02
Populus, 500 поколений0.171.600.330.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 невыгодна (на пороге — ничья); на плотных данных бывают ложные короткие куски.
  • Нужны фазированные данные и для цели, и для референсов.
  • Панель решает: TSI/LWK, 1 → 100 гаплотипов на популяцию — точность 41% → 98%.
  • λ без биологического смысла: зависит от мутаций и рекомбинации «сложным образом» — отсюда ансамбль.
Results и Discussion, Dias-Alves et al. 2018; веса — код bcm-uga/Loter @ 5c91354

Итог

Три мысли

  • LAI = одномерная сегментация. Loter минимизирует несовпадения + λ · переключения донора.
  • Динамическое программирование находит точный минимум за O(2n · p): внутренний минимум по строкам считается один раз на столбец.
  • λ задаёт разрешение: вставка B внутри постоянного A выживает при d > 2λ. Поэтому решает плотность SNP, а выбор λ снимает ансамбль из 160 решений.

Спасибо! Вопросы?

Dias-Alves T., Mairal J., Blum M.G.B. (2018) MBE 35(9):2318–2326, doi:10.1093/molbev/msy126 · github.com/bcm-uga/Loter