BWA总结.docxVIP

BWA的设计思想??2010-12-14 16:53:58|??分类： 二代测序 |??标签：序列比对??二代测序??bwa??burrows-wheeler转换?? |字号?订阅 BWA（Burrows-Wheeler Aligner?）是一款十分优秀的序列比对软件。它主要应用二代测序后的大量短小片段与参考基因组之间的定位比对。能够以较小的空间代价和时间代价，获得令人满意的比对效果。这里就其设计的基本原理作一较为详细的阐述。同时，bowtie软件的设计思想亦可参考本文。后缀树和后缀数组●文本后缀给定一个字母表Σ，x，Y，z是字母表Σ上的字符串，且x=yz，我们称y是x的前缀，z是x的后缀。如果我们把文本看作一个长的字符串，则文本的某后缀就是从特定位置起至文本结束所包含的字符串。如果要查找模式P，我们只要找到文本对应的所有以P开头的后缀即可。●Trie结构Trie是一种树形结构，它可以保存一组字符串。如果我们想要查找模式P，我们只需要O(|p|)的时间复杂度，跟Trie中保存了多少字符串无关。在Trie结构中，每个叶结点代表一个字符串，一个内部结点对应一个或多个字符串的前缀，有一条标记为字符C的边从前缀s所代表的节点指向SC所代表的节点。在查找Trie结构时，我们根据模式P中 的字符从根节点开始逐个字符的查找，如果查找最后到达某个叶结点，则说明我们找到了这个字符串；如果查找在某个节点无法继续下去，则说明字符串集合中不存 在查找的模式；如果查找在某个内部节点终止，则说明查找模式是某个或某些字符串的前缀。我们可以很容易的确定字符串集合中以模式P为前缀的所有字符串，按照上述的查找过程，我们查找最后到达某个内部节点，则以该节点为根的所有子树所代表的字符串集都是以模式P作为前缀。如果从一个节点到叶节点的路径没有分支，我们可以把所有节点压缩到叶节点以节省空间。我们可以把文本的所有后缀组成字符串集合来建立Trie结构如图2-1，并且在每个后缀尾部添加一个字符$，使没有一个后缀是另一个后缀的前缀，从而在建立的Trie结构中每个叶结点都对应唯一一个后缀字符串。这种Trie结构称为后缀Trie。后缀树是从后缀Trie变化而来的，它把单分支的路径压缩成一个节点，从而达到节省空间的目的。后缀树的建立算法可以参照有关的论文。后缀树相对于后缀Trie来说减少了空间占用，但是对于实际应用来说占用空问仍然过大，并且它的随机访问特性不适合于在辅助存储中保存。因此，一般来说后缀树对于大规模的文本查询只具有理论上的意义。?2-1 后缀树?后缀数组如图2-2很好的弥补了后缀树结构的不足之处，是用来查找大文本的有效数据结构。后缀数组只包含有序的后缀指针，每个后缀指针指向一个文本后缀，所有的后缀已经按照字典顺序排列。比如，对于文本alabr_a_alabrd#”，它的所有后缀指针为(0，1，2，3，4，5，6，7，8，9，10，11，12，13，14)，对应的后缀分别为(alabr_a_alabrd#，labra_alabrd#，abr_a_alabrd#，bra_alabrd#，r_a_alabrd#，a_alabrd#，a_alabrd#，_alabrd#，alabrd#，labrd#，abrd#，brd#，rd#，d#，#)对所有后缀按照字典顺序排序，结果为(#，a alabrd#，_alabrd#，aalabrd#，abraalabrd#，abrd#，alabr_a_alabrd#，alabrd#，br_a_alabrd#，brd#，d#，labr_a_alabrd#，labrd#，r_a_alabrd#，rd#)，对应的后缀指针为(14，5，7，6，2，10，0，8，3，11，13，1，9，4，12)，从而后缀数组为(14，5，7，6，2，10，0，8，3，11，13，1，9，4，12)。 上述过程通过排序所有后缀完成后缀数组的建立过程，更加复杂的算法可以参考有关的论文。在查找后缀数组时，因为所有后缀都已经按照字典顺序排列，我们可以 通过二分法查找指定的模式子串。当所有后缀按照字典顺序排列好以后，具有相同前缀的后缀位于后缀数组的连续区域，我们可以使用两个指针来标示这个连续区域 的位置（起始位置和结束位置），从而以模式子串在后缀数组中一次查询的代价查询到以某一模式开头的所有后缀字符串。这里的连续区域，类似于文献“Fast and accurate short read alignment with Burrows–Wheeler transform“中提到的suffix array interval，即后缀数据区间。因此，二代测序的序列比对就等同于查询参考序列的所有子序列中与测序获得的短小序列相匹配的后缀数组区间。如果是精确匹配，应该有且仅有一个这样的区间存在，