← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 8194.a.1.b · 生成模型:未记录

测序比对瓶颈

理解等级:中级

若有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个碱基错配呢?即使只是暂存,我们也要考虑如何储存这样庞大的信息?为了解决这个问题,我们需要建立索引,采用类似于电话簿的方式,查找部分匹配的序列,并记录每个读长的最佳匹配。搜索算法就是这样利用索引和筛选步骤来避免计算爆炸的。 这些搜索算法通常与能够容忍间隔与错配的比对程序结合在一起