Efficient and effective methods for variant selection

Variation graphs succinctly capture genetic variations among individuals within a species or a target population. The use of variation graphs instead of a single reference genome is credited with reducing bias and increasing the accuracy of sequence mapping algorithms. However, complete variation graphs that comprehensively incorporate all genetic variations are often found to be ineffective and inaccurate in practice due to the presence of a combinatorially explosive number of paths in the graph that do not correspond to any observed genome. Thus, a balance is struck in carefully selecting a subset of variants to be incorporated, for which mathematical frameworks have recently been developed. We advance the mathematical framework proposed by Jain et al.[Bioinformatics, 37 (2021)], where integer linear programming formulations were developed for optimal variant selection. We propose novel graph-based formulations and develop exact and fast algorithms for certain cases, approximation methods for some others, and empirically close to optimal results in all cases. The primary advantage of the algorithms designed here is that they provide near-optimal results at orders of magnitude faster run time of an ILP solver.