Developing fast algorithm for analyzing Giga-sequence data

下一代测序（NGS）技术需要快速准确的算法来评估大量数据的序列相似性。在这项研究中，我们设计并实现了精确的算法SlideSort，从NGS数据中找到编辑距离不超过给定阈值的所有相似对，这有助于许多重要的分析，如从头基因组组装，识别频繁出现的序列模式和准确聚类。与最先进的方法相比，我们的方法在寻找远程匹配方面要快得多，可以轻松扩展到数千万个序列。我们的软件增加了一个单链路聚类功能，这对总结NGS数据进行进一步处理很有用。

Next Generation Sequencing(NGS) technology calls for fast and accurate algorithms that can evaluate sequence similarity for a huge amount data. In this study, we designed and implemented exact algorithm SlideSort that finds all similar pairs whose edit-distance does not exceed a given threshold from NGS data, which helps many important analyses, such as de novo genome assembly, identification of frequently appearing sequence patterns and accurate clustering. In comparison to state-of-the-art methods, 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 NGS data for further processing.