多基因组索引研究及其改进序列比对算法

• 作 者: 何忠峭 徐云
• 机 构: 中国科学技术大学计算机科学与技术学院,安徽省高性能计算重点实验室,国防科学技术大学高性能计算协同创新中心
• 出 处: 计算机工程
• 发表日期: 2018年3期
• 关键词: 序列比对 个人基因组计划 千人基因组计划 下一代测序 多基因组算法 sequence alignment Personal Genome Project （P
• 基金项目: 国家自然科学基金面上项目（61672480）.

目前的多基因组比对算法需要大量时间和内存开销，多基因组索引（MuGI）的比对算法速度较快，但未能利用多基因组重复信息。为此，提出一种改进的MuGI索引比对算法。运用带单核苷酸多态性剪枝的动态种子扩展算法及多基因组的重复信息，提高比对速度。同时采用按需读取索引的内存管理策略，提高算法的空间效率。实验结果表明，改进算法仅需6GB运行内存，即可在1092人基因组上进行比对，并且误配阈值为5的比对速度为MuGI算法的3倍左右。