title: A comparison study of succinct data structures for use in GWAS.
abstract: BACKGROUND
  In recent years genetic data analysis has seen a rapid increase in the scale of data to be analyzed. Schadt et al (NRG 11:647-657, 2010) offered that with data sets approaching the petabyte scale, data related challenges such as formatting, management, and transfer are increasingly important topics which need to be addressed. The use of succinct data structures is one method of reducing physical size of a data set without the use of expensive compression techniques. In this work, we consider the use of 2- and 3-bit encoding schemes for genotype data. We compare the computational performance of allele or genotype counting algorithms utilizing genotype data encoded in both schemes.
  
  
  RESULTS
  We perform a comparison of 2- and 3-bit genotype encoding schemes for use in genotype counting algorithms. We find that there is a 20% overhead when building simple frequency tables from 2-bit encoded genotypes. However, building pairwise count tables for genome-wide epistasis is 1.0% more efficient.
  
  
  CONCLUSIONS
  In this work, we were concerned with comparing the performance benefits and disadvantages of using more densely packed genotype data representations in Genome Wide Associations Studies (GWAS). We implemented a 2-bit encoding for genotype data, and compared it against a more commonly used 3-bit encoding scheme. We also developed a C++ library, libgwaspp, which offers these data structures, and implementations of several common GWAS algorithms. In general, the 2-bit encoding consumes less memory, and is slightly more efficient in some algorithms than the 3-bit encoding.
authors.affiliation: Experimental Computing Lab, School of Electronic and Computing Systems, PO Box 210030, Cincinnati, OH 45221-0030, USA. putnampp@gmail.com.
authors.forename: Patrick P
authors.initials: PP
authors.lastname: Putnam
authors.forename: Ge
authors.initials: G
authors.lastname: Zhang
authors.forename: Philip A
authors.initials: PA
authors.lastname: Wilsey
mesh_terms: D000465:Algorithms; D044962:Data Compression; D015894:Genome, Human; D055106:Genome-Wide Association Study / Q000379:methods*; D005838:Genotype; D006801:Humans