bioRxiv Science⌕ Search
Home/Archive/bioRxiv

bioRxiv · 10.1101/103325

Ultra-fast Identity by Descent Detection in Biobank-Scale Cohorts using Positional Burrows-Wheeler Transform

Naseri, A.·Liu, X.·Zhang, S.·Zhi, D.
View original source ↗Export metadata ↓

Abstract

With the availability of genotyping data of very large samples, there is an increasing need for tools that can efficiently identify genetic relationships among all individuals in the sample. One fundamental measure of genetic relationship of a pair of individuals is identity by descent (IBD), chromosomal segments that are shared among two individuals due to common ancestry. However, the efficient identification of IBD segments among a large number of genotyped individuals is a challenging computational problem. Most existing methods are not feasible for even thousands of individuals because they are based on pairwise comparisons of all individuals and thus scale up quadratically with sample size. Some methods, such as GERMLINE, use fast dictionary lookup of short seed sequence matches to achieve a near-linear time efficiency. However, the number of short seed matches often scales up super-linearly in real population data.\n\nIn this paper we describe a new approach for IBD detection. We take advantage of an efficient population genotype index, Positional BWT (PBWT), by Richard Durbin. PBWT achieves linear time query of perfectly identical subsequences among all samples. However, the original PBWT is not tolerant to genotyping errors which often interrupt long IBD segments into short fragments. We introduce a randomized strategy by running PBWTs over random projections of the original sequences. To boost the detection power we run PBWT multiple times and merge the identified IBD segments through interval tree algorithms. Given a target IBD segment length, RaPID adjust parameters to optimize detection power and accuracy.\n\nSimulation results proved that our tool (RaPID) achieves almost linear scaling up to sample size and is orders of magnitude faster than GERMLINE. At the same time, RaPID maintains a detection power and accuracy comparable to existing mainstream algorithms, GERMLINE and IBDseq. Running multiple times with various target detection lengths over the 1000 Genomes Project data, RaPID can detect population events at different time scales. With our tool, it is feasible to identify IBDs among hundreds of thousands to millions of individuals, a sample size that will become reality in a few years.

Explore related subjects

genomicsPreprint

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Naseri, A., Liu, X., Zhang, S., Zhi, D.. 2017-01-26. Ultra-fast Identity by Descent Detection in Biobank-Scale Cohorts using Positional Burrows-Wheeler Transform. https://doi.org/10.1101/103325

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

KEEP EXPLORING

Related preprints

bioRxiv2026

Gene Embedding Hub: a standardized resource for human gene representations

Gene embeddings are vector representations of gene identity that provide machine-learning models with information from diverse biological sources. However, their use is hindered by a lack of standardization: inconsistent identifiers, formats, and preprocessing conventions. In this work, we present a unified resource of 67 human gene-embedding sets derived from protein, DNA and RNA sequences, biomedical text, bulk expression data, single-cell expression models, functional data, biological networks, knowledge graphs, regulatory genomics and multimodal models, covering up to 20,097 GENCODE-annotated protein-coding genes. The collection includes both published precomputed embeddings and representations generated or extracted from publicly available models and biological data. Each embedding set is organized in a folder containing the embedding matrix, the Ensembl gene identifiers, machine-readable metadata, and processing documentation. We validate the resource by measuring global and local similarity, cross-embedding consensus, and cross-embedding predictability. The collection is designed to allow community-contributed embeddings that meet predefined technical and documentation requirements, enables comparison of gene representations across modalities and provides standardized embeddings for training and downstream applications.

genomics↗
bioRxiv2026

Twenty-five new microsporidian genomes: Insights into ploidy, reproduction, and the group's pangenome

Microsporidia are single-celled, obligately intracellular eukaryotic parasites of growing importance. Many aspects of their biology remain enigmatic, partly because of difficulties in sampling, culturing, and experimentally manipulating them. Here, we continue efforts to generate microsporidian genomes from serendipitously infected organisms sequenced for biodiversity genomics initiatives, such as the Darwin Tree of Life Project. We present 25 new microsporidian genomes: 14 biologically complete, including several at (near-)chromosome level, and 11 partial. Using RNA-seq data for three published genomes we identify Prokka as a suitable ab initio annotation approach for Microsporidia. Consistently annotating all available genomes, we investigate gene-content diversity across microsporidian clades. We find that the microsporidian pangenome exhibits extreme diversity, and that current genomic data substantially undersample the group's proteome space. Neither GC content nor genome span consistently explains orthogroup number across lineages, suggesting different evolutionary pressures. We find few one-to-one orthogroups in Microsporidia, as well as few orthogroups that are both lineage-specific and conserved across most species within a given lineage. Finally, Hi-C data confirm that tetraploid Amblyosporida microsporidia occur as two equivalent diploid units. In contrast, one Enterocytozoonida tetraploid genome suggests that all four genome copies occur within a single nucleus (a 'monokaryon'), confirming a previous proposal.

genomics↗
bioRxiv2026

The Braarudosphaera bigelowii genome reveals cellular remodeling around a nitrogen-fixing organelle

Braarudosphaera bigelowii hosts the nitrogen-fixing cyanobacterial organelle UCYN-A, or the nitroplast, but the absence of a reference genome has limited investigation of the genomic features accompanying this association. Here, we present nuclear and organellar genome resources for the cultured B. bigelowii strain FR-21. The assembly comprises a 472.1-Mb nuclear genome together with representative nitroplast, chloroplast, and mitochondrial genomes of 1.49 Mb, 107 kb, and 44 kb, respectively. The four genomic compartments have strongly differentiated GC compositions, consistent with their distinct evolutionary origins. The large nuclear genome does not appear to reflect a corresponding expansion of protein-coding capacity. Repeat annotation indicates that approximately 77% of the nuclear assembly is repetitive, leaving approximately 108 Mb of nonrepetitive sequence containing roughly 16,000 predicted protein-coding genes. Phylogenomic analysis places B. bigelowii within the expected diversity of haptophytes, indicating that its unusual diazotrophic lifestyle is not associated with an anomalous phylogenetic position. Comparative analysis of nitrogen metabolism genes reveals extensive remodeling of host nitrogen acquisition and assimilation. B. bigelowii lacks major components required for nitrate and nitrite assimilation and has reduced capacity to use urea, cyanate, and several internally recycled nitrogen sources. In contrast, ammonium transport and the glutamine synthetase-glutamate synthase pathway are retained. This combination suggests reduced flexibility in nitrogen use and a host metabolism increasingly centered on ammonium supplied by the nitroplast. B. bigelowii also encodes an expanded set of flavodoxin and cryptochrome genes. Eleven of 14 flavodoxin candidates and 21 of 39 cryptochrome candidates contained motifs linked to nitroplast targeting. Together with previous evidence that some of these proteins are abundantly imported into the nitroplast, these expansions point to host-encoded roles in nitroplast redox metabolism and diel regulation. These genome resources establish a foundation for investigating nitroplast protein import, host-organelle metabolic integration, and the genomic consequences of acquiring an intracellular nitrogen-fixing compartment. They further show that the evolution of the B. bigelowii-UCYN-A relationship involved substantial remodeling of genome architecture and nitrogen metabolism in both partners.

genomics↗