Algorithmic Improvements for Modern Sequencing Technologies: Long-Read Polishing, Alignment, and Single-Cell Clustering

Abstract

Sequence analysis involves the examination and interpretation of genetic and genomic data, particularly the order of nucleotides, adenine, cytosine, guanine, and thymine, in DNA and RNA molecules. Accurate and precise sequence analysis is critical, as it enables the detection of genetic variations and mutations linked to diseases such as cancer and informs the development of effective treatments. This dissertation presents a multi-faceted approach to enhancing modern sequencing pipelines, addressing four complementary problems across long-read and single-cell technologies.

First, we investigate the per-base quality scores produced by Pacific Biosciences high fidelity (HiFi) circular consensus sequencing. By comparing these scores against a validation dataset, we identify systematic deviations from empirical error rates and describe a deep learning method, TopoQual, that corrects these discrepancies through topological analysis of partial order alignment graphs combined with learned recalibration. The improved scores are validated on an umbilical cord blood sample and shown to track empirical error rates more closely than both the original PacBio scores and DeepConsensus, while simultaneously polishing approximately 32% of the errors present in the input consensus reads.

Second, we address the computational cost of partial order alignment (POA), the multiple sequence alignment method that underlies both consensus generation and the proposed quality score recalibration. While POA preserves more information than sequential pairwise alignment, its quadratic time and memory complexity make it impractical on long reads such as PacBio HiFi. We extend the longest common subsequence with k-mer matches (LCSk++) algorithm to graph structures and present LCSkPOA, a banded POA method that achieves up to a 60 times speedup over unbanded SPOA on long synthetic sequences while maintaining alignment accuracy above 99% on real HiFi data.

Third, we focus on the demultiplexing of pooled single-cell ribonucleic acid sequencing (scRNA-seq) data, specifically enhancing the clustering performance of the Souporcell method. Existing genotype-based demultiplexing tools were primarily designed and benchmarked on pools of 16 or fewer donors, beyond which clustering quality degrades sharply. We present Souporcell3, which combines a 10x-merge cluster initialization strategy, deterministic annealing-enhanced K-Harmonic Means clustering, and iterative refinement with bad-cluster reinitialization and good-cluster locking. Souporcell3 achieves near-perfect adjusted Rand index scores and zero incorrectly merged clusters at donor counts of up to 64, substantially outperforming Vireo, overclustered Vireo, and the original Souporcell.

Fourth, we extend the clustering paradigm to spatial single-cell transcriptomics, where the goal shifts from demultiplexing donors to assigning cells to anatomically distinct tissue domains. By analysing Slide-seqV2 mouse cerebellum and Visium human dorsolateral prefrontal cortex (DLPFC) data under a suite of probabilistic models, we show that the negative binomial likelihood and generalised linear model principal component analysis (GLM-PCA) embedding exhibit complementary failure modes: the negative binomial loss is precise but has narrow range, while GLM-PCA provides wide global separation but is insensitive to small gene-level differences between transcriptionally similar layers. Motivated by this observation, we present SpaceCell, a three-stage method that first clusters cells with a Gaussian mixture model on the GLM-PCA embedding, then refines the partition by iteratively selecting the most representative cells under a negative-binomial discriminability score, and finally assigns the remaining cells using Leiden community detection on a graph whose edge weights combine negative binomial dissimilarity with spatial distance. SpaceCell improves cluster assignment accuracy over baseline k-means++ and Gaussian mixture model clustering on both datasets and offers a flexible framework for emerging spatial platforms such as Slide-seq and Visium HD.

Together, these contributions improve the accuracy, efficiency, and applicability of sequence analysis pipelines across both long-read and single-cell technologies, with direct implications for variant calling, genome assembly, and population-scale single-cell studies.