Biology subjects

Naseri, A.

Publications and source records attributed to Naseri, A..

13 recordsLinked to original sources

bioRxiv2026

Sum-h2, enabling genetic discovery for deep learning-derived phenotypes through a fast evaluation framework and arena of performance

In the recent growing interest of AI research toward biology, genetic association studies of AI- derived phenotypes from high-content modalities such as images emerges as a powerful means for biological discovery. However, such AI-phenotyping methods still lacks a good optimization target and an efficient evaluation framework. The number of discovered loci was the major criterion for evaluating the quality of AI-derived phenotypes. However, the time and computational resources required for running the GWAS and subsequent loci-clumping are substantial, limiting the rapid development and iteration of deep learning representation algorithms. Here we present a 1000x faster and lightweight framework, sum-h2, than traditional GWAS framework for evaluating genetic discovery through total heritability. We revisit tr(P^(-1) G), previously proposed in the context of evolutionary studies, as a measure of multi-phenotype heritability. We showed that sum-h2, the sum of heritability over phenotypic Principal Components (PCs), is equivalent to the linear transformation-invariant tr(P^(-1) G), through both theoretical proof and simulation studies. Moreover, sum-h2 can be estimated rapidly with minimal information loss over a relatedness-enriched sample, while preserving the relative ranking of endophenotypes by GWAS loci counts. Based on selected UKB data and sum-h2, we set up a Genetic Discovery Arena, enabling rapid and fair comparisons for the development and optimization of deep learning-derived phenotyping methods.

bioinformatics↗

bioRxiv2026

SLAB: A Sweep Line Algorithm in PBWT for Finding Haplotype Block Cores

With the increasing availability of high-quality phased haplotype data, researchers can more effectively identify detailed patterns of haplotype sharing and investigate the population genetic processes that shape them. In this work, we define block cores as genomic segments where multiple haplotype blocks overlap. We develop an efficient algorithm to analyze haplotype blocks, focusing on width-maximal matches and the identification of haplotype block cores. We apply our algorithm to UK Biobank haplotypes to quantify block cores and demonstrate the biological and population-level insights that can be inferred from their patterns. Specifically, identified block cores can serve as a basis for detecting signals of selection. Although our results are largely consistent with those from methods such as IBD rate analysis, they also reveal complementary information not captured by IBD rates or other conventional approaches. Source code is available at https://github.com/ZhiGroup/SLAB.

bioinformatics↗

bioRxiv2026

RLBWT-Based LCP Computation in Compressed Space for Terabase-Scale Pangenome Analysis

Lossless full text indexes are utilized in a myriad of applications in bioinformatics. The continuously decreasing cost of generating biological data has resulted in the need to build full text indexes on biological datasets of increasing size. Many compressed full text indexes have been developed to address this problem. In particular, run-length Burrows-Wheeler transform (RLBWT) based compressed full text indexes have seen wide development and adoption. However, the construction of these RLBWT-based compressed full text indexes is still computationally expensive, sometimes prohibitively so, even for current dataset sizes. Therefore, we present algorithms for the construction of RLBWT-based compressed full text indexes and their supporting data structures in compressed space. The algorithms have a space complexity of O(r) words and run in O(n) time for repetitive datasets, where r is the number of runs in the BWT, n is the length of the text, and repetitive datasets implies the average run length is at least log n. We provide the first algorithm to compute LCP-related information for repetitive datasets in optimal time and O(r) space, greatly reducing memory requirements. The key idea behind this algorithm is the utilization of r samples of the inverse suffix array at regular intervals. For example, on the Human Pangenome Reference Consortium Release 2 dataset, this reduces peak memory from 2,135 GiB to 170 GiB (12.6x reduction) compared to the previous best method (pfp-thresholds). AvailabilityThe implementation is available at https://github.com/ucfcbb/TeraTools. Supplementary InformationSupplementary Material is available online at bioRxiv.

bioinformatics↗

bioRxiv2024

Local Haplotype Classifiers enable Efficient, Flexible, and Secure Genotype Imputation and Downstream Analyses

The decreasing cost of genotyping technologies led to abundant availability and usage of genetic data. Although it offers many potentials for improving health and curing diseases, genetic data is highly intrusive in many aspects of individual privacy. Secure genotype analysis methods have been developed to perform numerous tasks such as genome-wide association studies, meta-analysis, kinship inference, and genotype imputation outsourcing. Here we present a new approach for using lightweight haplotype classifier models to use predicted haplotype information in a flexible privacy-preserving framework to perform genotype imputation and downstream tasks. Compared to the previous secure methods that rely main on linear models, our approach utilizes efficient models that rely on utilizing haplotypic information, which improves accuracy and increases the throughput of imputation by performing multiple imputations per model evaluation.

bioinformatics↗

bioRxiv2023

FastRecomb: Fast inference of genetic recombination rates in biobank scale data

While rates of recombination events across the genome (genetic maps) are fundamental to genetic research, the majority of current studies only use one standard map. There is evidence suggesting population differences in genetic maps, and thus estimating population-specific maps are of interest. While the recent availability of biobank-scale data offers such opportunities, current methods are not efficient at leveraging very large sample sizes. The most accurate methods are still linkage-disequilibrium (LD)-based methods that are only tractable for a few hundred samples. In this work, we propose a fast and memory-efficient method for estimating genetic maps from population genotyping data. Our method, FastRecomb, leverages the efficient positional Burrows-Wheeler transform (PBWT) data structure for counting IBD segment boundaries as potential recombination events. We used PBWT blocks to avoid redundant counting of pairwise matches. Moreover, we used a panel smoothing technique to reduce the noise from errors and recent mutations. Using simulation, we found that FastRecomb achieves state-of-the-art performance at 10k resolution, in terms of correlation coefficients between the estimated map and the ground truth. This is mainly due to the fact that FastRecomb can effectively take advantage of large panels comprising more than hundreds of thousands of haplotypes. At the same time, other methods lack the efficiency to handle such data. We believe further refinement of FastRecomb would deliver more accurate genetic maps for the genetics community.

bioinformatics↗

bioRxiv2022

mcPBWT: Space-efficient Multi-column PBWT Scanning Algorithm for Composite Haplotype Matching

Positional Burrows-Wheeler Transform (PBWT) is a data structure that supports efficient algorithms for finding matching segments in a panel of haplotypes. It is of interest to study the composite patterns of multiple matching segments or blocks arranged contiguously along a same haplotype as they can indicate recombination crossover events, gene-conversion tracts, or, some-times, errors of phasing algorithms. However, current PBWT algorithms do not support search of such composite patterns efficiently. Here, we present our algorithm, mcPBWT (multi-column PBWT), that uses multiple synchronized runs of PBWT at different variant sites providing a "look-ahead" information of matches at those variant sites. Such "look-ahead" information allows us to analyze multiple contiguous matching pairs in a single pass. We present two specific cases of mcPBWT, namely double-PBWT and triple-PBWT which utilize two and three columns of PBWT respectively. double-PBWT finds two matching pairs combinations representative of crossover event or phasing error while triple-PBWT finds three matching pairs combinations representative of gene-conversion tract.

bioinformatics↗

bioRxiv2022

RaPID-Query for Fast Identity by Descent Search and Genealogical Analysis

The size of genetic databases has grown large enough such that, genetic genealogical search, a process of inferring familial relatedness by identifying DNA matches, has become a viable approach to help individuals finding missing family members or law enforcement agencies locating suspects. However, a fast and accurate method is needed to search an out-of-database individual against millions of individuals in such databases. Most existing approaches only offer all-vs-all within panel match. Some prototype algorithms offer 1-vs-all query from out-of-panel individual, but they do not tolerate errors. A new method, random projection-based identical-by-descent (IBD) detection (RaPID) query, referred as RaPID-Query, is introduced to make fast genealogical search possible. RaPID-Query method identifies IBD segments between a query haplotype and a panel of haplotypes. By integrating matches over multiple PBWT indexes, RaPID-Query method is able to locate IBD segments quickly with a given cutoff length while allowing mismatched sites in IBD segments. A single query against all UK biobank autosomal chromosomes can be completed within 2.76 seconds CPU time on average, with the minimum 7 cM IBD segment length and minimum 700 markers. Using the same criteria, RaPID-Query can achieve 0.099 false negative rate and 0.017 false positive rate at the same time on a chromosome 20 sequencing panel having 92,296 sites, which is comparable to the state-of-the-art IBD detection method Hap-IBD. For the relatedness degree separation experiments, RaPID-Query is able to distinguish up to fourth degree of the familial relatedness for a given individual pair, and the area under the receiver operating characteristic curve values are at least 97.28%. It is anticipated that RaPID-Query will make genealogical search convenient and effective, potentially with the integration of complex inference models.

bioinformatics↗

bioRxiv2022

Syllable-PBWT for space-efficient haplotype long-match query

The positional Burrows-Wheeler transform (PBWT) has led to tremendous strides in haplotype matching on biobank-scale data. For genetic genealogical search, PBWT-based methods have optimized the asymptotic runtime of finding long matches between a query haplotype and a predefined panel of haplotypes. However, to enable fast query searches, the full-sized panel and PBWT data structures must be kept in memory, preventing existing algorithms from scaling up to modern biobank panels consisting of millions of haplotypes. In this work, we propose a space-efficient variation of PBWT named Syllable-PBWT, which divides every haplotype into syllables, builds the PBWT positional prefix arrays on the compressed syllabic panel, and leverages the polynomial rolling hash function for positional substring comparison. With the Syllable-PBWT data structures, we then present a long match query algorithm named Syllable-Query. Compared to Algorithm 3 of Sanaullah et al. (2021), the most time- and space-efficient previously published solution to the long match query problem, Syllable-Query reduced the memory use by a factor of over 100 on both the UK Biobank genotype data and the 1000 Genomes Project sequence data. Surprisingly, the smaller size of our syllabic data structures allows for more efficient iteration and CPU cache usage, granting Syllable-Query even faster runtime than existing solutions. The implementation of our algorithm is available at https://github.com/ZhiGroup/Syllable-PBWT.

bioinformatics↗

bioRxiv2020

Simultaneous Epigenetic Perturbation and Genome Imaging Reveal Distinct Roles of H3K9me3 in Chromatin Architecture and Transcription

Despite the long-observed correlation between H3K9me3, chromatin architecture and transcriptional repression, how H3K9me3 regulates genome higher-order organization and transcriptional activity in living cells remains unclear. Here we develop EpiGo (Epigenetic perturbation induced Genome organization)-KRAB to introduce H3K9me3 at hundreds of loci spanning megabases on human chromosome 19 and simultaneously track genome organization. EpiGo-KRAB is sufficient to induce de novo heterochromatin-like domain formation, which requires SETDB1, a methyltransferase of H3K9me3. Unexpectedly, EpiGo-KRAB induced heterochromatin-like domain does not result in widespread gene repression except a small set of genes with concurrent loss of H3K4me3 and H3K27ac. Ectopic H3K9me3 appears to spread in inactive regions but is largely restricted to transcriptional initiation sites in active regions. Finally, Hi-C analysis showed that EpiGo-KRAB induced to reshape existing compartments. These results reveal the role of H3K9me3 in genome organization could be partially separated from its function in gene repression.

molecular biology↗

bioRxiv2020

CRISPR-based Live Imaging of Epigenetic Modification-Mediated Genome Reorganization

Epigenetic modifications play an essential role in chromatin architecture and dynamics. The role of epigenetic modification in chromatin organization has been studied by Hi-C from population cells, but imaging techniques to study their correlation and regulation in single living cells are lacking. Here we develop a CRISPR-based EpiGo (Epigenetic perturbation induced Genome organization) system to track epigenetic modification-mediated relocation, interaction or reorganization of genomic regions in living cells. EpiGo-KRAB is sufficient to induce the relocation of genomic loci to HP1 condensates and trigger genomic interactions. EpiGo-KRAB also triggers the induction of H3K9me3 at large genomic regions, which decorate on the surface of HP1 condensates possibly driven by phase separation.

molecular biology↗

bioRxiv2019

Personalized genealogical history inferred from biobank-scale IBD segments

When modern biobanks collect genotype information for a significant fraction of a population, dense genetic connections of a person can be traced using identity by descent (IBD) segments. These connections offer opportunities to characterize individuals in the context of the underlying populations. Here, we conducted an individual-centric analysis of IBDs among the UK Biobank participants that represent 0.7% of the UK population. On average, one UK individual shares IBDs over 5 cM with 14,000 UK Biobank participants, which we refer to as "cousins". Using these segments, approximately 80% of a persons genome can be reconstructed. Also, using changes of cousin counts sharing IBDs at different lengths, we identified a group, potentially British Jews, who has a distinct pattern of familial expansion history. Finally, using the enrichment of cousins in ones neighborhood, we identified regional variations of personal preference favoring living closer to ones extended families. In summary, our analysis revealed genetic makeup, personal genealogical history, and social behaviors at population scale, opening possibilities for further studies of individuals genetic connections in biobank data.

genetics↗

bioRxiv2017

CRISPR-Based DNA Imaging in Living Cells Reveals Cell Cycle-Dependent Chromosome Dynamics

In contrast to the well-studied condensation and folding of chromosomes during mitosis, their dynamics in interphase are less understood. We developed a sensitive, multicolor system, CRISPR-Sirius, allowing the real-time tracking of the dynamics of chromosomal loci. We tracked loci kilobases to megabases apart and found significant variation in the inter-locus distances of each pair, indicating differing degrees of DNA contortion. We resolved two distinct modes of dynamics of loci: saltatory local movements as well as translational movements of the domain. The magnitude of both of these modes of movements increased from early to late G1, whereas the translational movements were reduced in early S. The local fluctuations decreased slightly in early S and more markedly in mid-late S. These newly observed movements and their cell cycle-dependence are indicative of a hitherto unrecognized compaction-relaxation dynamic of the chromosomal fiber operating concurrently with changes in the extent of observed genomic domain movements.\n\nIN BRIEFDistinct chromosome folding and dynamics during cell cycle progression were dissected by CRISPR-Sirius DNA imaging in living cells.\n\nHIGHLIGHTSO_LICRISPR-Sirius allows tracking of pairs of chromosomal loci having kilobase to megabase inter-locus distances\nC_LIO_LIPair-wise tracking of loci allows measurement of both local and domain dynamics\nC_LIO_LIChromosomal fiber relaxation is positively correlated with local dynamics\nC_LIO_LIGenomic region size contributes to local and domain movements\nC_LIO_LIDistinct chromosome dynamics were uncovered during cell cycle progression in interphase\nC_LI

cell biology↗

bioRxiv2017

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

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.

genomics↗