知识卡片
测序比对瓶颈
若有N条读段、参考序列长度为L,逐读段逐候选位置比较就会产生约N×L个候选,且每次比较仍有成本。索引先缩小可能匹配的位置,再用容忍错配或间隔的算法精细比较,可避免直接穷举。书中数量示例是候选空间的说明,不是实测CPU指令数或所有流程的固定瓶颈。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 信息革命对生物学研究的影响 测序范围、三层分析与变异推断 · 查看原书依据
从概念上讲,我们可以将每个读长与基因组中的每个位置进行比对。对于一个100bp的读长,通过一次移动一个碱基,我们将进行3×109次比较。这种糟糕的搜索策略需要我们以非常低效的形式进行3×1018 次操作。同时,我们还有可能找不到完全匹配的序列;如果每100bp读长包含1个、2个或3个碱基错配呢?即使只是暂存,我们也要考虑如何储存这样庞大的信息?为了解决这个问题,我们需要建立索引,采用类似于电话簿的方式,查找部分匹配的序列,并记录每个读长的最佳匹配。搜索算法就是这样利用索引和筛选步骤来避免计算爆炸的。 这些搜索算法通常与能够容忍间隔与错配的比对程序结合在一起
参考来源
- 位置:《人工智能与计算生物的未来 (【美】布赖恩·希尔布什)》信息革命对生物学研究的影响,测序范围、三层分析与变异推断(源项目a19c7933-4eda-4176-aebd-30fe7e1ad292,源文件:extracted/人工智能与计算生物的未来 (【美】布赖恩·希尔布什)/_epub-src/EPUB/xhtml/Section02.xhtml)
- 结论依据:原文对该概念的说明、比较或案例支撑本卡解释;历史案例不等于当前临床有效性或监管认可。已经核验的边界与书中陈述分开。
- 原始内容:从概念上讲,我们可以将每个读长与基因组中的每个位置进行比对。对于一个100bp的读长,通过一次移动一个碱基,我们将进行3×109次比较。这种糟糕的搜索策略需要我们以非常低效的形式进行3×1018 次操作。同时,我们还有可能找不到完全匹配的序列;如果每100bp读长包含1个、2个或3个碱基错配呢?即使只是暂存,我们也要考虑如何储存这样庞大的信息?为了解决这个问题,我们需要建立索引,采用类似于电话簿的方式,查找部分匹配的序列,并记录每个读长的最佳匹配。搜索算法就是这样利用索引和筛选步骤来避免计算爆炸的。 这些搜索算法通常与能够容忍间隔与错配的比对程序结合在一起