title: Assembly-free genome comparison based on next-generation sequencing reads and variable length patterns.
abstract: BACKGROUND
  With the advent of Next-Generation Sequencing technologies (NGS), a large amount of short read data has been generated. If a reference genome is not available, the assembly of a template sequence is usually challenging because of repeats and the short length of reads. When NGS reads cannot be mapped onto a reference genome alignment-based methods are not applicable. However it is still possible to study the evolutionary relationship of unassembled genomes based on NGS data.
  
  
  RESULTS
  We present a parameter-free alignment-free method, called Under2, based on variable-length patterns, for the direct comparison of sets of NGS reads. We define a similarity measure using variable-length patterns, as well as reverses and reverse-complements, along with their statistical and syntactical properties. We evaluate several alignment-free statistics on the comparison of NGS reads coming from simulated and real genomes. In almost all simulations our method Under2 outperforms all other statistics. The performance gain becomes more evident when real genomes are used.
  
  
  CONCLUSIONS
  The new alignment-free statistic is highly successful in discriminating related genomes based on NGS reads data. In almost all experiments, it outperforms traditional alignment-free statistics that are based on fixed length patterns.
authors.forename: Matteo
authors.initials: M
authors.lastname: Comin
authors.forename: Michele
authors.initials: M
authors.lastname: Schimd
mesh_terms: D000465:Algorithms; D000818:Animals; D001105:Archaea / Q000235:genetics; D001419:Bacteria / Q000235:genetics; D004330:Drosophila / Q000235:genetics; D016678:Genome; D023281:Genomics / Q000379:methods*; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D015233:Models, Statistical; D010363:Pattern Recognition, Automated; D010802:Phylogeny; D017422:Sequence Analysis, DNA / Q000379:methods*