- 针对母序列构建BWT序列，在母序列末尾添加一个$符循环右移，每次移动一位。得到n（n为母序列长度）个长度为n的序列。
- n个序列按字典序排序，形成BWT阵列。
- 取每个序列的最后一位，从上到下拼在一起，即为BWT串。
- 取待查找子串的最后一位字符x，在BWT阵列左侧第1列查找该字符x，获取该行最后一位字符k，若该行末尾k为BWT最后一列中的第n个k，则在BWT阵列左侧第一列寻找第n个k，取该行末尾为新的k，循环，若循环过程中每一个k形成的序列与待查子串的逆序不匹配则退出循环，若一直匹配，则m次操作后停止（m为待查子串长度），停止时k所在的行数即为待查子串在母串中的位置。
-
Notifications
You must be signed in to change notification settings - Fork 1
hitlxc/BWT
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
About
基于BWT字符匹配算法的基因检索程序
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published