title: CGAP-align: a high performance DNA short read alignment tool.
abstract: BACKGROUND
  Next generation sequencing platforms have greatly reduced sequencing costs, leading to the production of unprecedented amounts of sequence data. BWA is one of the most popular alignment tools due to its relatively high accuracy. However, mapping reads using BWA is still the most time consuming step in sequence analysis. Increasing mapping efficiency would allow the community to better cope with ever expanding volumes of sequence data.
  
  
  RESULTS
  We designed a new program, CGAP-align, that achieves a performance improvement over BWA without sacrificing recall or precision. This is accomplished through the use of Suffix Tarray, a novel data structure combining elements of Suffix Array and Suffix Tree. We also utilize a tighter lower bound estimation for the number of mismatches in a read, allowing for more effective pruning during inexact mapping. Evaluation of both simulated and real data suggests that CGAP-align consistently outperforms the current version of BWA and can achieve over twice its speed under certain conditions, all while obtaining nearly identical results.
  
  
  CONCLUSIONS
  CGAP-align is a new time efficient read alignment tool that extends and improves BWA. The increase in alignment speed will be of critical assistance to all sequence-based research and medicine. CGAP-align is freely available to the academic community at http://sourceforge.net/p/cgap-align under the GNU General Public License (GPL).
authors.affiliation: School of Computer Science, Fudan University, Shanghai, China.
authors.forename: Yaoliang
authors.initials: Y
authors.lastname: Chen
authors.forename: Ji
authors.initials: J
authors.lastname: Hong
authors.forename: Wanyun
authors.initials: W
authors.lastname: Cui
authors.forename: Jacques
authors.initials: J
authors.lastname: Zaneveld
authors.forename: Wei
authors.initials: W
authors.lastname: Wang
authors.forename: Richard
authors.initials: R
authors.lastname: Gibbs
authors.forename: Yanghua
authors.initials: Y
authors.lastname: Xiao
authors.forename: Rui
authors.initials: R
authors.lastname: Chen
mesh_terms: D000465:Algorithms; D001483:Base Sequence / Q000235:genetics*; D059014:High-Throughput Nucleotide Sequencing / Q000639:trends*; D016415:Sequence Alignment / Q000379:methods*; D012984:Software