title: Using reference-free compressed data structures to analyze sequencing reads from thousands of human genomes.
abstract: We are rapidly approaching the point where we have sequenced millions of human genomes. There is a pressing need for new data structures to store raw sequencing data and efficient algorithms for population scale analysis. Current reference-based data formats do not fully exploit the redundancy in population sequencing nor take advantage of shared genetic variation. In recent years, the Burrows-Wheeler transform (BWT) and FM-index have been widely employed as a full-text searchable index for read alignment and de novo assembly. We introduce the concept of a population BWT and use it to store and index the sequencing reads of 2705 samples from the 1000 Genomes Project. A key feature is that, as more genomes are added, identical read sequences are increasingly observed, and compression becomes more efficient. We assess the support in the 1000 Genomes read data for every base position of two human reference assembly versions, identifying that 3.2 Mbp with population support was lost in the transition from GRCh37 with 13.7 Mbp added to GRCh38. We show that the vast majority of variant alleles can be uniquely described by overlapping 31-mers and show how rapid and accurate SNP and indel genotyping can be carried out across the genomes in the population BWT. We use the population BWT to carry out nonreference queries to search for the presence of all known viral genomes and discover human T-lymphotropic virus 1 integrations in six samples in a recognized epidemiological distribution.
authors.affiliation: Wellcome Trust Sanger Institute, Hinxton, Cambridge CB10 1SA, United Kingdom.
authors.forename: Dirk D
authors.initials: DD
authors.lastname: Dolle
authors.affiliation: Wellcome Trust Sanger Institute, Hinxton, Cambridge CB10 1SA, United Kingdom.|European Bioinformatics Institute, Hinxton, Cambridge CB10 1SD, United Kingdom.
authors.forename: Zhicheng
authors.initials: Z
authors.lastname: Liu
authors.affiliation: Wellcome Trust Sanger Institute, Hinxton, Cambridge CB10 1SA, United Kingdom.
authors.forename: Matthew
authors.initials: M
authors.lastname: Cotten
authors.affiliation: Ontario Institute for Cancer Research, Toronto, Ontario M5G 0A3, Canada.|Department of Computer Science, University of Toronto, Toronto, Ontario M5S 3G4, Canada.
authors.forename: Jared T
authors.initials: JT
authors.lastname: Simpson
authors.affiliation: Wellcome Trust Centre for Human Genetics, Oxford OX3 7BN, United Kingdom.
authors.forename: Zamin
authors.identifier: 0000-0001-8466-7547
authors.initials: Z
authors.lastname: Iqbal
authors.affiliation: Wellcome Trust Sanger Institute, Hinxton, Cambridge CB10 1SA, United Kingdom.
authors.forename: Richard
authors.initials: R
authors.lastname: Durbin
authors.affiliation: Wellcome Trust Sanger Institute, Hinxton, Cambridge CB10 1SA, United Kingdom.
authors.forename: Shane A
authors.initials: SA
authors.lastname: McCarthy
authors.affiliation: Wellcome Trust Sanger Institute, Hinxton, Cambridge CB10 1SA, United Kingdom.|European Bioinformatics Institute, Hinxton, Cambridge CB10 1SD, United Kingdom.
authors.forename: Thomas M
authors.identifier: 0000-0001-7532-6898
authors.initials: TM
authors.lastname: Keane
mesh_terms: D000483:Alleles; D044962:Data Compression; D015894:Genome, Human / Q000235:genetics*; D023281:Genomics; D005838:Genotype; D006801:Humans; D054643:INDEL Mutation / Q000235:genetics; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA; D012984:Software; D000073336:Whole Genome Sequencing / Q000379:methods*