Fast and accurate large multiple sequence alignments using root-to-leave regressive computation

Garriga Nogales, E.; Di Tommaso, P.; Magis, C.; Erb, I.; Laayouni, H.; Kondrashov, F.; Floden, E.; Notredame, C.

doi:10.1101/490235

Home/Archive/bioRxiv

bioRxiv · 10.1101/490235

Fast and accurate large multiple sequence alignments using root-to-leave regressive computation

Garriga Nogales, E.·Di Tommaso, P.·Magis, C.·Erb, I.·Laayouni, H.·Kondrashov, F.·Floden, E.·Notredame, C.

View original source ↗Export metadata ↓

Abstract

Inferences derived from large multiple alignments of biological sequences are critical to many areas of biology, including evolution, genomics, biochemistry, and structural biology. However, the complexity of the alignment problem imposes the use of approximate solutions. The most common is the progressive algorithm, which starts by aligning the most similar sequences, incorporating the remaining ones following the order imposed by a guide-tree. We developed and validated on protein sequences a regressive algorithm that works the other way around, aligning first the most dissimilar sequences. Our algorithm produces more accurate alignments than non-regressive methods, especially on datasets larger than 10,000 sequences. By design, it can run any existing alignment method in linear time thus allowing the scale-up required for extremely large genomic analyses.\n\nOne Sentence SummaryInitiating alignments with the most dissimilar sequences allows slow and accurate methods to be used on large datasets

Explore related subjects

bioinformatics Preprint

Keep this discovery

Explore connections, maps & timelines

BibTeX RIS

Garriga Nogales, E., Di Tommaso, P., Magis, C., Erb, I., Laayouni, H., Kondrashov, F., Floden, E., Notredame, C.. 2018-12-07. Fast and accurate large multiple sequence alignments using root-to-leave regressive computation. https://doi.org/10.1101/490235

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

KEEP EXPLORING

Related preprints

bioRxiv2026

A comparative transcriptomic framework across kidney organoid, assembloid, and transplantation models

Human kidney organoids recapitulate key aspects of renal development and have emerged as valuable platforms for disease modeling, nephrotoxicity screening, and therapeutic development. The field now includes a wide range of emerging protocols with distinct cellular compositions and maturation states, which complicates systematic comparison and model selection. Here, we integrated single-cell and single-nucleus transcriptomes from 11 studies spanning kidney organoid and assembloids, both in vitro and following transplantation, benchmarked against fetal and adult kidney references. Transcriptional maturation toward adult identity is compartment specific and does not correlate with protocol complexity. Assembloid protocols show the most adult-like podocyte and distal nephron signatures, transplantation is associated with enhanced tubular oxidative metabolic features, only protocols incorporating ureteric progenitors reliably generate collecting-duct lineages, and no protocol achieves mature adult proximal tubule identity. Annotating against either fetal or adult kidney reference alone leads to misassignment, because early fetal nephron epithelium transcriptionally resembles injury-dedifferentiated adult proximal tubule cells. Assembloid and transplantation models share elevated mechanosensing pathway expression independently of vascularization. Together, these findings provide a framework for kidney organoid model selection.

bioinformatics↗

bioRxiv2026

OncoSpot enables benchmarking of cancer spatial transcriptomics methods across tumor evolutionary modes

Spatial transcriptomics (ST) is increasingly used to map clonal architecture within tumors, yet methods for analyzing cancer ST data are difficult to evaluate because real tumors lack ground truth for copy-number alterations (CNAs), subclonal identity, and malignant cell fraction. Existing ST simulators model normal tissue and do not represent tumor evolution, CNA-driven expression, or the spatial organization of malignant subclones. We present OncoSpot, a cancer-aware simulator of Visium-like spot-based ST data. OncoSpot combines a spatial evolutionary scaffold from DEMON, CNAs generated along the resulting clonal phylogeny with CNAsim, cancer-type-specific malignant transcriptional programs, and spatially clustered nonmalignant cell types, and aggregates cells into spots with known malignant fraction, subclone, and copy-number profiles. We demonstrate OncoSpot on high-grade serous ovarian carcinoma, colorectal cancer, and hepatocellular carcinoma, which represent three distinct modes of tumor evolution. Simulated subclones were spatially clustered and showed stronger phylogeny-space concordance than those generated by scCube under matched subclone populations. Benchmarking CopyKAT, CancerFinder, Clonalscope, and RCTD revealed cancer-dependent performance: Clonalscope recovered copy-number signals more accurately in ovarian and colorectal cancer, whereas CopyKAT performed better in hepatocellular carcinoma, reflecting both the assumptions of each method and the copy-number landscapes of the three cancers. OncoSpot's ground truth also exposed a failure mode in Clonalscope's malignant spot identification, in which tumor and normal labels were inverted, and allowed us to trace its cause. These method-dependent behaviors would be difficult to detect in real data. OncoSpot provides a framework for benchmarking CNA inference, subclone detection, malignant spot identification, and normal spot deconvolution, and its modular design and guidelines allow extension to additional cancer types. OncoSpot is freely available at https://github.com/compbio-mallory/OncoSpot.

bioinformatics↗

bioRxiv2026

PartiDesign: A structure-sequence co-design paradigm for practical all-to-all biomolecules design

Engineering interactions among biomolecules offers a route to creating new biological functions. Although unified models have advanced biomolecular structure prediction and design, efficient and controllable generation across molecular modalities remains challenging. A key challenge is to couple three-dimensional structure generation with sequence or chemical-identity design across chemically diverse systems. Here, we introduce PartiDesign, a unified structure-sequence co-design model that extends the partially latent framework of La-Proteina to proteins, nucleic acids and small molecules. PartiDesign jointly generates molecular structures and their corresponding sequences or chemical identities, while providing fine-grained control over secondary structure, chemical bonding and amino acid preferences. Across diverse benchmarks for the de novo design of proteins, nucleic acids and small molecules against specified targets, PartiDesign achieved the highest estimated successful-design throughput among the evaluated methods on most benchmarks under the adopted compute-budget protocols. Its configurable constraints further support cyclic peptide and antibody design, allowing generation to be tailored to specific structural and chemical requirements. PartiDesign was developed using 128 Huawei Ascend 910B accelerators, each with 64 GB of memory. The source code is available at https://github.com/MegaGatlingPea/PartiDesign-official, and a freely accessible web server at https://cadd.zju.edu.cn/partidesign/ enables users to generate binding partners without programming expertise. Together, these capabilities provide a versatile and accessible framework for all-to-all biomolecular design, with applications in molecular engineering and drug discovery.

bioinformatics↗