title: Next generation sequencing reads comparison with an alignment-free distance.
abstract: BACKGROUND
  Next Generation Sequencing (NGS) machines extract from a biological sample a large number of short DNA fragments (reads). These reads are then used for several applications, e.g., sequence reconstruction, DNA assembly, gene expression profiling, mutation analysis.
  
  
  METHODS
  We propose a method to evaluate the similarity between reads. This method does not rely on the alignment of the reads and it is based on the distance between the frequencies of their substrings of fixed dimensions (k-mers). We compare this alignment-free distance with the similarity measures derived from two alignment methods: Needleman-Wunsch and Blast. The comparison is based on a simple assumption: the most correct distance is obtained by knowing in advance the reference sequence. Therefore, we first align the reads on the original DNA sequence, compute the overlap between the aligned reads, and use this overlap as an ideal distance. We then verify how the alignment-free and the alignment-based distances reproduce this ideal distance. The ability of correctly reproducing the ideal distance is evaluated over samples of read pairs from Saccharomyces cerevisiae, Escherichia coli, and Homo sapiens. The comparison is based on the correctness of threshold predictors cross-validated over different samples.
  
  
  RESULTS
  We exhibit experimental evidence that the proposed alignment-free distance is a potentially useful read-to-read distance measure and performs better than the more time consuming distances based on alignment.
  
  
  CONCLUSIONS
  Alignment-free distances may be used effectively for reads comparison, and may provide a significant speed-up in several processes based on NGS sequencing (e.g., DNA assembly, reads classification).
authors.affiliation: Department of Engineering, Roma Tre University, Via della Vasca Navale 79, 00146 Rome, Italy. emanuel@dia.uniroma3.it.
authors.forename: Emanuel
authors.initials: E
authors.lastname: Weitschek
authors.forename: Daniele
authors.initials: D
authors.lastname: Santoni
authors.forename: Giulia
authors.initials: G
authors.lastname: Fiscon
authors.forename: Maria Cristina
authors.initials: MC
authors.lastname: De Cola
authors.forename: Paola
authors.initials: P
authors.lastname: Bertolazzi
authors.forename: Giovanni
authors.initials: G
authors.lastname: Felici
mesh_terms: D000465:Algorithms; D004269:DNA, Bacterial / Q000737:chemistry / Q000235:genetics*; D004271:DNA, Fungal / Q000737:chemistry / Q000235:genetics*; D004926:Escherichia coli / Q000235:genetics; D059014:High-Throughput Nucleotide Sequencing; D006801:Humans; D012441:Saccharomyces cerevisiae / Q000235:genetics; D016415:Sequence Alignment / Q000379:methods / Q000706:statistics & numerical data*; D017422:Sequence Analysis, DNA / Q000379:methods / Q000706:statistics & numerical data*
chemical_list: D004269:DNA, Bacterial; D004271:DNA, Fungal