SlideSort: all pairs similarity search for short reads.
SlideSort: all pairs similarity search for short reads.
复制标题
SlideSort：所有对相似性搜索短读。
DOI：
10.1093/bioinformatics/btq677
复制
发表时间：
2011-02-15
期刊：
影响因子：
--
通讯作者：
Tsuda K
中科院分区：
文献类型：
--
作者：
Shimizu K;Tsuda K
动机：DNA测序技术的最新进展要求快速准确的算法，可以评估大量短读段的序列相似性。从字符串池中搜索相似对是从头基因组组装、全基因组比对等重要分析的基本过程。结果如下：在这项研究中，我们设计并实现了一个精确的算法SlideSort，从一个字符串池中找到所有相似的编辑距离。使用一个有效的模式增长算法，SlideSort发现链的共同k-mer缩小搜索。与现有的基于单k-mer的方法相比，我们的方法更有效地减少了编辑距离计算的数量。与BWA等回溯方法相比，我们的方法在查找远程匹配方面要快得多，可以轻松扩展到数千万个序列。我们的软件具有单链接聚类的附加功能，这在总结短读段以供进一步处理时很有用。可用性：可执行二进制文件和C++库可在http://www.cbrc.jp/~shimizu/slidesort/上获得Linux和Windows。联系方式：slidesort@m.aist.go.jp; shimizu-kana@aist.go.jp补充信息：补充数据可在生物信息学在线获得。
Motivation: Recent progress in DNA sequencing technologies calls for fast and accurate algorithms that can evaluate sequence similarity for a huge amount of short reads. Searching similar pairs from a string pool is a fundamental process of de novo genome assembly, genome-wide alignment and other important analyses. Results: In this study, we designed and implemented an exact algorithm SlideSort that finds all similar pairs from a string pool in terms of edit distance. Using an efficient pattern growth algorithm, SlideSort discovers chains of common k-mers to narrow down the search. Compared to existing methods based on single k-mers, our method is more effective in reducing the number of edit distance calculations. In comparison to backtracking methods such as BWA, our method is much faster in finding remote matches, scaling easily to tens of millions of sequences. Our software has an additional function of single link clustering, which is useful in summarizing short reads for further processing. Availability: Executable binary files and C++ libraries are available at http://www.cbrc.jp/~shimizu/slidesort/ for Linux and Windows. Contact: slidesort@m.aist.go.jp; shimizu-kana@aist.go.jp Supplementary information: Supplementary data are available at Bioinformatics online.
登录
查看更多内容
影响因子：
5.8
作者：
Warren, Rene L.;Sutton, Granger G.;Holt, Robert A.
通讯作者：
Holt, Robert A.
影响因子：
5.8
作者：
Jiang, Hui;Wong, Wing Hung
通讯作者：
Wong, Wing Hung
影响因子：
2.2
作者：
Rajasekaran, Sanguthevar;Balla, Sudha;Schiller, Martin
通讯作者：
Schiller, Martin
影响因子：
7
作者：
Simpson, Jared T.;Wong, Kim;Birol, Inanc
通讯作者：
Birol, Inanc
影响因子：
12.3
作者：
Langmead B;Trapnell C;Pop M;Salzberg SL
通讯作者：
Salzberg SL