Minimal Positional Substring Cover: A Haplotype Threading Alternative to Li & Stephens Model

Sanaullah, A.; Zhi, D.; Zhang, S.

doi:10.1101/2023.01.04.522803

Home/Archive/bioRxiv

bioRxiv · 10.1101/2023.01.04.522803

Minimal Positional Substring Cover: A Haplotype Threading Alternative to Li & Stephens Model

Sanaullah, A.·Zhi, D.·Zhang, S.

View original source ↗Export metadata ↓

Abstract

The Li & Stephens (LS) hidden Markov model (HMM) models the process of reconstructing a haplotype as a mosaic copy of haplotypes in a reference panel (haplotype threading). For small panels the probabilistic parameterization of LS enables modeling the uncertainties of such mosaics, and has been the foundational model for haplotype phasing and imputation. However, LS becomes inefficient when sample size is large (tens of thousands to millions), because of its linear time complexity (O(MN), where M is the number of haplotypes and N is the number of sites in the panel). Recently the PBWT, an efficient data structure capturing the local haplotype matching among haplotypes, was proposed to offer fast methods for giving some optimal solution (Viterbi) to the LS HMM. But the solution space of the LS for large panels is still elusive. Previously we introduced the Minimal Positional Substring Cover (MPSC) problem as an alternative formulation of LS whose objective is to cover a query haplotype by a minimum number of segments from haplotypes in a reference panel. The MPSC formulation allows the generation of a haplotype threading in time constant to sample size (O(N)). This allows haplotype threading on very large biobank scale panels on which the LS model is infeasible. Here we present new results on the solution space of the MPSC by first identifying a property that any MPSC will have a set of required regions, and then proposing a MPSC graph. In addition, we derived a number of optimal algorithms for MPSC, including solution enumerations, the Length Maximal MPSC, and h-MPSC solutions. In doing so, our algorithms reveal the solution space of LS for large panels. Even though we only solved an extreme case of LS where the emission probability is 0, our algorithms can be made more robust by PBWT smoothing. We show that our method is informative in terms of revealing the characteristics of biobank-scale data sets and can improve genotype imputation.

Source connections

Published article ↗

Explore related subjects

bioinformatics Preprint

Keep this discovery

Explore connections, maps & timelines

BibTeX RIS

Sanaullah, A., Zhi, D., Zhang, S.. 2023-01-06. Minimal Positional Substring Cover: A Haplotype Threading Alternative to Li & Stephens Model. https://doi.org/10.1101/2023.01.04.522803

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related preprints

bioRxiv2026

Comparative functional genomics reveals distributed SERPINE1 like characteristics among Drosophila serpins

Serpins (serine protease inhibitors) regulate proteolytic activity through a suicide-substrate inhibitory mechanism, whereby the serpin covalently traps and inactivates their target protease. Serpins are broadly conserved across eukaryotes, but the evolutionary and functional relationships between human SERPINE1, and Drosophila Serpins in incompletely defined. To identify candidate Drosophila functional analogs of SERPINE1/PAI-1, a multi-omics framework was applied to thoroughly compare the serpins across species. The multi-level analysis integrated orthology prediction, protein sequence and structural characterization, phylogenetic reconstruction, bulk tissue transcriptomics, single-cell transcriptomics, and aging-associated expression analysis. Candidate serpins (Spn42Da, Spn42Db, Spn42Dc, Spn42Dd, Spn28B, and Spn28F) were evaluated using DIOPT, AlphaFold/ChimeraX structural comparisons, reactive center loop analyses, phylogenetic distances, GTEx, Human Protein Atlas, FlyAtlas2, Fly Cell Atlas, and Aging Fly Cell Atlas datasets. Comparative analyses demonstrated full-length sequence and reactive center loop (RCL) divergence despite preservation of the canonical serpin fold. Tissue, cell-type, and age-associated expression analysis revealed distinct candidate-specific patterns. Spn42Dd comparisons uncovered similarities to human SERPINE1 in sequence/structural and broad expression but did not represent the strongest overall cross-species expression correlations. Spn42Da and Spn42Db received the highest cross species integrated support. Quality check of the ranking confirmed that Spn42Da and Spn42Db were stable top candidates across orthology, sequence alignment, and expression domains. The multi-domain analysis was unable to identify a single definitive Drosophila serpin as the closest counterpart to human SERPINE1, indicating that cross-species similarity is distributed across multiple candidate serpins. This study therefore provides a quantitative method for prioritizing potential evolutionary and functional analogs across highly divergent species.

bioinformatics↗

bioRxiv2026

CellChat Hotspot: A Targeted Approach to Cell Cell Communication Analysis With Spatial transcriptomics Validation.

Abstract. In recent years, single cell RNA sequencing (scRNA seq) has enabled the investigation of intercellular communication through Cell Cell Communication (CCC) tools such as CellChat. Despite their potential, these approaches remain challenging to interpret, particularly when global analyses generate complex interaction networks that may include biologically irrelevant signals. To address this limitation, we developed a framework termed CellChat Hotspot, designed to improve the biological interpretability of inferred communication networks. This approach integrates gene set enrichment analysis with a context driven filtering strategy, selecting both genes and cells based on their functional relevance prior to communication inference. Applied to stage II colon cancer data, CellChat Hotspot enabled the identification of condition-specific interaction patterns associated with recurrence. Non recurrent patients showed enrichment of immune related processes, whereas recurrent cases were characterized by pathways associated with invasion and metastasis. Notably, a loss of interaction in the HSPG pathway between CALB1+ and stromal cells was observed in recurrent patients, suggesting a potential disruption of cell matrix adhesion mechanisms. To verify the reliability of this finding, we applied the framework to spatial transcriptomics data, which confirmed the presence of the HSPG2 DAG1 interaction in non-recurrent tumors and its near absence in recurrent ones. Overall, this framework provides a biologically guided strategy for studying intercellular communication in complex systems such as the tumor microenvironment.

bioinformatics↗

bioRxiv2026

DiffTernary: a Diffusion Model for Molecular Glue Ternary Complex Docking

Molecular glues (MGs) modulate protein function by inducing or stabilizing protein interactions. However, accurately modeling MG ternary complexes remains challenging. Here, we present DiffTernary, a diffusion-based docking method for the joint prediction of relative protein arrangement and MG binding pose. We introduce Ternary-PDB, a dataset of 76,702 experimentally determined ternary complexes curated from the Protein Data Bank using structural filters and a release cutoff aligned with AlphaFold 3 (AF3). When trained on this dataset, DiffTernary achieved acceptable protein-protein interaction (PPI) predictions (DockQ > 0.23) for 50.0% of MGBench complexes with a single prediction, compared with 51.1% for AF3. In comparisons with AF3, OpenFold3, ESMFold2, Protenix-v1 and Protenix-v2, DiffTernary ranked second with a best-of-25 PPI prediction success rate of 78.4%, behind ESMFold2 (90.9%) and ahead of AF3 (72.7%). A separate DiffTernary model trained on TernaryDB achieved a mean DockQ of 0.306 on the 94 complexes in the TernaryDB MGD test set with a single prediction, compared with 0.228 for DeepTernary. Confidence-based selection among 40 samples yielded acceptable PPI predictions for 41.5% of complexes, compared with 30.9% for DeepTernary. An E2Former variant increased training and sampling throughput 6.90-fold and 4.37-fold, respectively, under the evaluated configurations. Together, DiffTernary and Ternary-PDB provide an efficient docking approach for MG complex prediction and a valuable structural resource for MG discovery and design.

bioinformatics↗