Using reference-free compressed data structures to analyze sequencing reads from thousands of human genomes

Area of Science:

• Genomics and Bioinformatics
• Computational Biology
• Data Structures and Algorithms

Background:

• The increasing volume of human genome sequencing data necessitates advanced data structures and algorithms for efficient storage and population-scale analysis.
• Existing reference-based formats do not fully leverage the redundancy and shared genetic variation present in population sequencing data.
• The Burrows-Wheeler transform (BWT) and FM-index are established tools for sequence alignment and assembly but require adaptation for population genomics.

Purpose of the Study:

• To introduce and implement a population Burrows-Wheeler transform (BWT) for storing and indexing large-scale human sequencing data.
• To assess the efficiency of the population BWT in terms of compression and data retrieval.
• To demonstrate the utility of the population BWT for variant genotyping and pathogen detection.

Main Methods:

• Development and application of a population Burrows-Wheeler transform (BWT) to index sequencing reads from 2705 samples in the 1000 Genomes Project.
• Assessment of data compression efficiency as the number of genomes increases.
• Analysis of human reference genome assembly support and variant allele representation using k-mers (31-mers).
• Implementation of SNP and indel genotyping and non-reference queries for viral genome detection.

Main Results:

• The population BWT demonstrates increasing compression efficiency with more genomes due to shared sequence redundancy.
• Comparison of human reference assemblies (GRCh37 vs. GRCh38) revealed significant differences in sequence support.
• The population BWT enables rapid and accurate SNP and indel genotyping across the dataset.
• Non-reference queries successfully identified human T-lymphotropic virus 1 integrations in six samples.

Conclusions:

• The population BWT is an effective data structure for managing and analyzing large-scale population sequencing data.
• This approach offers improved compression and facilitates efficient genomic analysis, including variant calling and pathogen discovery.
• The population BWT provides a scalable solution for future genomic studies with millions of samples.