title: Memory efficient assembly of human genome.
abstract: The ability to detect the genetic variations between two individuals is an essential component for genetic studies. In these studies, obtaining the genome sequence of both individuals is the first step toward variation detection problem. The emergence of high-throughput sequencing (HTS) technology has made DNA sequencing practical, and is widely used by diagnosticians to increase their knowledge about the casual factor in genetic related diseases. As HTS advances, more data are generated every day than the amount that scientists can process. Genome assembly is one of the existing methods to tackle the variation detection problem. The de Bruijn graph formulation of the assembly problem is widely used in the field. Furthermore, it is the only method which can assemble any genome in linear time. However, it requires an enormous amount of memory in order to assemble any mammalian size genome. The high demands of sequencing more individuals and the urge to assemble them are the driving forces for a memory efficient assembler. In this work, we propose a novel method which builds the de Bruijn graph while consuming lower memory. Moreover, our proposed method can reduce the memory usage by 37% compared to the existing methods. In addition, we used a real data set (chromosome 17 of A/J strain) to illustrate the performance of our method.
authors.affiliation: Department of Computer Science, University of California Los Angeles, Los Angeles, CA 90095, USA.
authors.forename: Farhad
authors.initials: F
authors.lastname: Hormozdiari
authors.forename: Eleazar
authors.initials: E
authors.lastname: Eskin
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology; D003198:Computer Simulation; D015894:Genome, Human; D059014:High-Throughput Nucleotide Sequencing / Q000706:statistics & numerical data*; D006801:Humans; D051379:Mice; D008805:Mice, Inbred A / Q000235:genetics; D009154:Mutation; D020641:Polymorphism, Single Nucleotide; D016415:Sequence Alignment / Q000706:statistics & numerical data; D017422:Sequence Analysis, DNA / Q000706:statistics & numerical data; D012984:Software
keywords: De Bruijn graph; Genome assembly; high-throughput sequencing; local assembly