Better spaced seeds using Quadratic Residues

作者：

Highlights：

• We build spaced seeds for approximate pattern matching using Quadratic Residues.

• Quadratic Residue seeds are lossless and work for any number of errors.

• Quadratic Residue seeds provably generate less false positives than single seeds.

摘要

•We build spaced seeds for approximate pattern matching using Quadratic Residues.•Quadratic Residue seeds are lossless and work for any number of errors.•Quadratic Residue seeds provably generate less false positives than single seeds.

论文关键词：Sequence comparison,Homology search,Approximate matching,Hamming distance,Spaced seeds,Lossless filtration

论文评审过程：Received 26 October 2012, Revised 25 January 2013, Accepted 12 March 2013, Available online 16 March 2013.

论文官网地址：https://doi.org/10.1016/j.jcss.2013.03.002