Methods for the alignment of sequence reads to non-acyclic genome graphs on heterogeneous computing systems

The disclosed embodiments concern methods, apparatus, systems, and computer program products for computing the best alignment score between a set of query sequences and a non-acyclic sequence-labelled reference genome graph comprising a processor and non-transitory memory. In an embodiment, said computing is performed employing an alignment algorithm suitable for non-acyclic graph that leverages inter-sequence and intra-sequence parallelism, executed on a heterogeneous computing system, containing at least a CPU (Central Processing Unit) and a GPU (Graphics Processing Units).