Nanopore Guided Assembly of Segmental Duplications Near Telomeres Human subtelomere regions are highly enriched in large segmental duplications and structural variants, leading to many gaps and misassemblies in these regions. We develop a novel method, NPGREAT (NanoPore Guided REgional Assembly Tool), which combines Nanopore ultralong read datasets and shortread assemblies derived from 10x linkedreads to efficiently assemble these subtelomere regions into a single continuous sequence. We show that with the use of ultralong Nanopore reads as a guide, the highly accurate shorter linkedread sequence contigs are correctly oriented, ordered, spaced and extended. In the rare cases where a linkedread sequence contig contains inaccurately assembled segments, the use of Nanopore reads allows for detection and correction of this error. We tested NPGREAT on four representative subtelomeres of the NA12878 human genome (10p, 16p, 19q and 20p). The results demonstrate that the final computed assembly of each subtelomere is accurate and complete.

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.