Minimum Segmentation for Pangenomic Founder Reconstruction in Linear Time Given a threshold L and a set R  R_1, ..., R_m of m strings (haplotype sequences), each having length n, the minimum segmentation problem for founder reconstruction is to partition 1,n into set P of disjoint segments such that each segment a,b in P has length at least L and the number d(a,b)R_ia,b : 1 u003c i u003c m of distinct substrings at segment a,b is minimized over a,b in P. The distinct substrings in the segments represent founder blocks that can be concatenated to form maxd(a,b) : a,b in P founder sequences representing the original R such that crossovers happen only at segment boundaries. We give an optimal O(mn) time algorithm to solve the problem, improving over earlier O(mn2). This improvement enables to exploit the algorithm on a pangenomic setting of input strings being aligned haplotype sequences of complete human chromosomes, with a goal of finding a representative set of references that can be indexed for read alignment and variant calling. We implemented the new algorithm and give some experimental evidence on the practicality of the approach on this pangenomic setting.

On the Complexity of Sequence to Graph Alignment Availability of extensive genetics data across multiple individuals and populations is driving the growing importance of graph based reference representations. Aligning sequences to graphs is a fundamental operation on several types of sequence graphs (variation graphs, assembly graphs, pangenomes, etc.) and their biological applications. Though research on sequence to graph alignments is nascent, it can draw from related work on pattern matching in hypertext. In this paper, we study sequence to graph alignment problems under Hamming and edit distance models, and linear and affine gap penalty functions, for multiple variants of the problem that allow changes in query alone, graph alone, or in both. We prove that when changes are permitted in graphs either standalone or in conjunction with changes in the query, the sequence to graph alignment problem is (mathcal NP)complete under both Hamming and edit distance models for alphabets of size (ge 2). For the case where only changes to the sequence are permitted, we present an (O(VmE)) time algorithm, where m denotes the query size, and V and E denote the vertex and edge sets of the graph, respectively. Our result is generalizable to both linear and affine gap penalty functions, and improves upon the runtime complexity of existing algorithms.