PASS: a program to align short sequences
PASS: a program to align short sequences
复制标题
DOI：
10.1093/bioinformatics/btp087
复制
发表时间：
2009-04-01
期刊：
影响因子：
5.8
通讯作者：
Valle, Giorgio
中科院分区：
文献类型：
--
作者：
Campagna, Davide;Albiero, Alessandro;Valle, Giorgio
标准 DNA 比对程序不足以管理新一代 DNA 测序仪产生的数据。为了解决这个问题，我们开发了 PASS，目的是与其他可用程序相比提高执行时间和灵敏度。 PASS 将短 DNA 序列与参考 DNA（通常是基因组序列）进行快速空位和无空位比对。它旨在处理大量读取，例如由 Solexa、SOLiD 或 454 技术生成的读取。该算法基于一种数据结构，该数据结构在 RAM 中保存种子词（通常为 11 和 12 个碱基）的基因组位置索引以及相互对齐的短词（通常为 7 和 8 个碱基）的预先计算分数的索引。构建基因组索引后，程序扫描每个查询序列，执行三个步骤：（1）在基因组中找到匹配的种子词； (2) 对于每场比赛，检查短侧翼区域的预先计算的对齐情况； (3)如果通过步骤2，则它对比赛周围的狭窄区域执行精确的动态对准。该程序的灵敏度和速度的性能都非常惊人。例如，间隙对齐的实现速度比 BLAST 快数百倍，比 SOAP 快几倍，特别是在允许间隙的情况下。此外，与其他可用程序相比，PASS 具有更高的灵敏度。
Standard DNA alignment programs are inadequate to manage the data produced by new generation DNA sequencers. To answer this problem, we developed PASS with the objective of improving execution time and sensitivity when compared with other available programs. PASS performs fast gapped and ungapped alignments of short DNA sequences onto a reference DNA, typically a genomic sequence. It is designed to handle a huge amount of reads such as those generated by Solexa, SOLiD or 454 technologies. The algorithm is based on a data structure that holds in RAM the index of the genomic positions of seed words (typically 11 and 12 bases) as well as an index of the precomputed scores of short words (typically seven and eight bases) aligned against each other. After building the genomic index, the program scans every query sequence performing three steps: (1) it finds matching seed words in the genome; (2) for every match checks the precomputed alignment of the short flanking regions; (3) if passes step 2, then it performs an exact dynamic alignment of a narrow region around the match. The performance of the program is very striking both for sensitivity and speed. For instance, gap alignment is achieved hundreds of times faster than BLAST and several times faster than SOAP, especially when gaps are allowed. Furthermore, PASS has a higher sensitivity when compared with the other available programs.