Scalable Graph Algorithms for Bioinformatics using Structure, Parameterization and Dynamic Updates

Introduction

Sequencing technologies have developed to be cheap and accurate, leading to major breakthroughs, such as the complete sequence of a human genome, the creation of nationwide population gene banks, or the discovery of novel viruses. As the amount of data produced grows exponentially and their applications become more broad and complex, the community needs accurate computational methods that scale.

Algorithmic Challenges

At the core of many algorithmic methods for processing sequencing data is the basic primitive of finding a set of paths or walks in graphs of various nature. Under different formulations and objective functions, the resulting problems can be:

1. NP-hard (e.g. flow decompositions)
2. Polynomial-time (e.g. path covers)

These challenges are impractical on large graphs. Thus, many practical tools prefer fast heuristics to exact algorithms. While these may be optimized for specific inputs, they may not be reliable or accurate in general, which is a highly relevant issue in, e.g., medical and life-science research.

Project Goals

This project will develop general methods to massively scale such exact graph algorithms. The approach will include:

1. Novel Graph Structures:

   • Safety structures, e.g., sets of paths that can be quickly found to appear in all optimal solutions and thus simplify the problem.
   • Variation structures that limit the hardness of a problem only to graph areas rich in genetic variation.

2. Modern Algorithmic Techniques:

   • Parameterizing polynomial algorithms to run in time linear in the graph size and superlinear only in a small parameter.
   • Dynamic algorithms that, as the input grows, update solutions based only on the new data.

Applications

We will apply these methods in two high-impact applications:

1. Long-read RNA transcript discovery
2. Indexing massive and rapidly growing genomic databases

Conclusion

This project paves the way for exact graph algorithms usable independently of the problem complexity or of the input size, applicable to real-world problems.