A CONTIG ASSEMBLY PROGRAM BASED ON SENSITIVE DETECTION OF FRAGMENT OVERLAPS
A CONTIG ASSEMBLY PROGRAM BASED ON SENSITIVE DETECTION OF FRAGMENT OVERLAPS
复制标题
DOI：
10.1016/s0888-7543(05)80277-0
复制
发表时间：
1992-09-01
期刊：
影响因子：
4.4
通讯作者：
HUANG, XQ
中科院分区：
文献类型：
--
作者：
HUANG, XQ
重叠群组装程序（CAP）是一种有效的DNA片段组装程序。在CAP程序中，使用过滤器来快速消除不可能重叠的片段对，应用动态规划算法来计算每个剩余片段对之间的最大得分重叠比对，并且采用简单的贪婪方法来按照比对得分的顺序组装片段。为了识别真正的片段重叠，动态编程算法使用专门选择的比对参数组来容忍测序错误并惩罚重复序列的不同拷贝之间的“突变”变化。该程序在基因组测序项目的片段数据上的性能测试产生了令人满意的结果。CAP程序在计算机时间和内存中是高效的;在Sun工作站上将一组1015个片段组装成长重叠群花费了大约4小时。
An effective computer program for assembling DNA fragments, the contig assembly program (CAP), has been developed. In the CAP program, a filter is used to eliminate quickly fragment pairs that could not possibly overlap, a dynamic programming algorithm is applied to compute the maximal-scoring overlapping alignment between each remaining pair of fragments, and a simple greedy approach is employed to assemble fragments in order of alignment scores. To identify the true fragment overlaps, the dynamic programming algorithm uses specially chosen sets of alignment parameters to tolerate sequencing errors and to penalize “mutational” changes between different copies of a repetitive sequence. The performance tests of the program on fragment data from genomic sequencing projects produced satisfactory results. The CAP program is efficient in computer time and memory; it took about 4 h to assemble a set of 1015 fragments into long contigs on a Sun workstation.