Выравнивание последовательностей с учётом гаплотипов на графах пангенома

Современные графы пангенома строятся на основе сборок генома с разрешением гаплотипов. При картировании ридов на граф пангенома приоритет выравниваний, согласующихся с известными гаплотипами, повышает точность генотипирования. Однако существующие строгие формулировки задач построения коллинеарных цепочек и выравнивания не учитывают гаплотипные пути в графе пангенома. Это часто приводит к ложным выравниваниям ридов на путях, соответствующих маловероятным рекомбинациям известных гаплотипов. В этой работе мы предлагаем новые формулировки и алгоритмы для задач выравнивания последовательности с графом и построения цепочек. Основываясь на моделях импутации генотипов, мы предполагаем, что искомая последовательность представляет собой несовершенную мозаику референсных гаплотипов. Поэтому в целевые функции вводится штраф за рекомбинацию при каждом переключении гаплотипа. Во-первых, мы решаем задачу выравнивания последовательности с графом с учётом гаплотипов за время [формула], где [формула] — искомая последовательность, [формула] — множество рёбер, а H — множество представленных в графе гаплотипов. В дополнение к этому решению мы доказываем, что в соответствии с гипотезой о сильной экспоненциальной временной сложности (SETH) невозможно создать алгоритм, существенно более быстрый, чем [формула]. Во-вторых, мы предлагаем алгоритм построения цепочек с учётом гаплотипов, работающий за время [формула] после предварительной обработки графа, где [формула] — число входных якорей. Затем мы показываем, что в соответствии с SETH невозможно создать алгоритм построения цепочек, существенно более быстрый, чем [формула]. В качестве доказательства применимости мы реализовали предложенный алгоритм построения цепочек в программе выравнивания Minichain. При выравнивании последовательностей, отобранных из главного комплекса гистосовместимости (MHC) человека, на граф пангенома, включающий 60 гаплотипов MHC, наш алгоритм продемонстрировал более высокое соответствие истинным рекомбинациям по сравнению с алгоритмом, не учитывающим гаплотипы.