GraphSlimmer: Preserving Read Mappability with the Minimum Number of Variants

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Modern genomic datasets (e.g., 1000 Genome Project) contain millions of variants, posing computational challenges for tasks like read mapping.
• Complete variant sets can decrease mapping accuracy and require substantial computational resources due to large genome graph data structures.

Purpose of the Study:

• To develop a technique for identifying a minimal subset of genomic variants.
• To ensure that all substrings up to a specified length (α) remain alignable with a bounded Hamming or edit distance (δ) using the reduced variant set.

Main Methods:

• Demonstrated the NP-hardness and inapproximability of variant subset selection optimization problems.
• Developed Integer Linear Programming (ILP) formulations for variant selection, including an edit distance formulation that decomposes the problem by variant locations.
• Scaled the edit distance ILP formulation to handle all variants of chromosome 22 from the 1000 Genome Project.

Main Results:

• Showed that a significant reduction in variants is achievable.
• For moderately long reads (α=1000), over 75% of variants can be removed while maintaining read mappability with an edit distance of at most one.
• The proposed ILP formulation successfully scaled to large-scale genomic data.

Conclusions:

• A minimal variant subset selection technique can drastically reduce computational burden for genomic analyses.
• The method preserves essential information for accurate read mapping, addressing limitations of using complete variant sets.
• This approach offers a computationally efficient alternative for analyzing large-scale genomic datasets.