GS-aligner: A novel tool for aligning genomic sequences using bit-level operations
GS-aligner: A novel tool for aligning genomic sequences using bit-level operations
复制标题
DOI：
10.1093/molbev/msg139
复制
发表时间：
2003-08-01
影响因子：
10.7
通讯作者：
Li, WH
中科院分区：
文献类型：
--
作者：
Shih, ACC;Li, WH
开发了一种使用位级操作的新颖算法 GS-Aligner，用于比对基因组序列。 GS-Aligner 在时间和空间上都非常高效，可以比对两个非常长的基因组序列以及识别基因组重排（例如易位和倒位）。它适用于比对相当不同的序列，例如人类和小鼠基因组序列。它由几个有效的组件组成：位级编码、搜索两个序列之间的匹配片段作为对齐锚、最长递增子序列（LIS）和最佳局部对齐。我们已努力减少程序的执行时间，使其真正适用于对齐很长的序列。经验测试表明，对于相对不同的序列，例如来自不同哺乳动物目或来自哺乳动物和非哺乳动物脊椎动物的序列，GS-Aligner 比现有方法表现更好。程序和数据可以从http://pondside.uchicago.edu/similar tolilab/和http://webcollab.iis.sinica.edu.tw/similar tobiocom下载。
A novel algorithm, GS-Aligner, that uses bit-level operations was developed for aligning genomic sequences. GS-Aligner is efficient in terms of both time and space for aligning two very long genomic sequences and for identifying genomic rearrangements such as translocations and inversions. It is suitable for aligning fairly divergent sequences such as human and mouse genomic sequences. It consists of several efficient components: bit-level coding, search for matching segments between the two sequences as alignment anchors, longest increasing subsequence (LIS), and optimal local alignment. Efforts have been made to reduce the execution time of the program to make it truly practical for aligning very long sequences. Empirical tests suggest that for relatively divergent sequences such as sequences from different mammalian orders or from a mammal and a nonmammalian vertebrate GS-Aligner performs better than existing methods. The program and data can be downloaded from http://pondside.uchicago.edu/similar tolilab/ and http:http://webcollab.iis.sinica.edu.tw/similar tobiocom.