计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2006年
1期
139-144
,共6页
序列拼接%欧拉超路%并行拼接%哈希表
序列拼接%歐拉超路%併行拼接%哈希錶
서렬병접%구랍초로%병행병접%합희표
序列拼接是全基因组测序的核心问题之一.基于"overlap-layout-consensus"的传统拼接软件虽然被人们应用于人类基因组拼接等项目,但它们始终不能有效解决全基因组重复序列的拼装问题.为了克服上述不足,Pevzner等提出了欧拉超路拼接算法.由于该算法要求构造一个复杂的de Bruijin图,因此用欧拉超路算法拼接大规模全基因组存在存储瓶颈问题.该文对欧拉超路拼接算法做了并行化研究并付诸实现,有效解决了欧拉超路算法中的存储瓶颈问题.测试结果表明,该并行算法具有良好的可扩缩性,能够解决较大规模全基因组的序列拼接.
序列拼接是全基因組測序的覈心問題之一.基于"overlap-layout-consensus"的傳統拼接軟件雖然被人們應用于人類基因組拼接等項目,但它們始終不能有效解決全基因組重複序列的拼裝問題.為瞭剋服上述不足,Pevzner等提齣瞭歐拉超路拼接算法.由于該算法要求構造一箇複雜的de Bruijin圖,因此用歐拉超路算法拼接大規模全基因組存在存儲瓶頸問題.該文對歐拉超路拼接算法做瞭併行化研究併付諸實現,有效解決瞭歐拉超路算法中的存儲瓶頸問題.測試結果錶明,該併行算法具有良好的可擴縮性,能夠解決較大規模全基因組的序列拼接.
서렬병접시전기인조측서적핵심문제지일.기우"overlap-layout-consensus"적전통병접연건수연피인문응용우인류기인조병접등항목,단타문시종불능유효해결전기인조중복서렬적병장문제.위료극복상술불족,Pevzner등제출료구랍초로병접산법.유우해산법요구구조일개복잡적de Bruijin도,인차용구랍초로산법병접대규모전기인조존재존저병경문제.해문대구랍초로병접산법주료병행화연구병부제실현,유효해결료구랍초로산법중적존저병경문제.측시결과표명,해병행산법구유량호적가확축성,능구해결교대규모전기인조적서렬병접.
