Ⅰ BWT比对算法
BWT算法在多款序列比对软件（BWA，bowtie）中都有涉及，那么对于RNA-seq的2代数据，一般建库长度是单端300bp，双端各150bp左右。
对于两个序列进行比对，即pairwise alignment，我们可以按比对方式分为全局比对（NW算法）和局部比对（SW算法）：
比方说SOAP：
它把参考基因组分成一个个小片段，并且将这些小片段建立成hash关系，也就是说我在序列比对的时候，只要我获取到reads的内容，我就可以match（翻译为完全比对？）到参考基因组上，并获得其位置信息。
这里介绍的是BWA，bowtie。而这两款软件除了要对基因组建立index以外，还采用的是BWT算法来实现比对。
step2 ：
之后，“$”符号向后平移一个单位，得到 :
“$”符号再向后平移一个单位:得到:
以此类推，最终得到：
这样的序列的排序表，接下来按照字母顺序进行排序（$,A,C,G,T）有：
这个矩阵我们称之为转换矩阵
我们根据F列和L列元素的相对位置就可以推导出该序列的全部信息：
首先，我们单独取出F列和L列
在F列和L列中找到“$”，连接它们，那么在水平位置对应于的G（蓝色箭头）
这个G就是“$”前面的元素:
接下来在F列中找到元素G：
此时按照上述方法，才F列中找到元素C，由于L列中的元素C为第二个C（上面G后面的C视为第一个C），所以应该对于F列的第二个C
接下来L列第三个A对应F列第三个A，因此以此类推就可以最终还原（最终对应于L列的$)：
比方说我现在有一条短序列CAA要比对到ACAACG上，首先说明的是在比对过程中，CAA是反向进行比对的，即A->A->C
由于CAA第一个比对的元素是A，在F列中有三个A，因此我们分类讨论
选择第一个A：
此时比对结果为ACA，不符合
选择第二个A：
结果为$，不符合
选择第三个A：
此时比对结果为CAA，符合原序列
在现实中，CAA可以想象为fq文件reads，ACAACG可以想象为参考基因组，并且在比对中会存在mismatch和gap这种情况的发生，因此软件会对每一种比对的情况进行打分，择优处理
目前 bowtie 是没有gap这一项设定的
参考： https://www.bilibili.com/video/av15743137/
刘小乐哈佛大学课程： https://www.bilibili.com/video/BV1De411s71p
https://www.bilibili.com/video/BV1d4411E7uS?from=search&seid=7482313674070699968
Ⅱ 10.12 bwa使用 安装文件路径与使用 sh权限
我们这里将用于流程构建的BWA就是其中最优秀的一个，它将BW(Burrows-Wheeler)压缩算法和后缀树相结合，能够让我们以较小的时间和空间代价，获得准确的序列比对结果。
别人的已安装文件打包传递后使用：
1、连接服务器
2、家目录下，Users，ls -all (或者 打开/etc里profile）
3、vim .bashrc
```
export PATH="your path:$PATH"
```
4、source .bashrc
5、在全局中输入bwa测试是否可以使用
自己安装的软件路径都已经配置好了，所以不需要这样操作就可以直接使用。
BWA MEM比对模块是有一定适用范围的：它是专门为长read比对设计的，目的是为了解决，第三代测序技术这种能够产生长达几十kb甚至几Mbp的read情况。一般只有当read长度≥70bp的时候，才推荐使用，如果比这个要小，建议使用BWA ALN模块。
BWA ALN模块
1: 建立 Index
根据reference genome data(e.g. reference.fa) 建立 Index File
bwa index -a bwtsw reference.fa
(bwa index 可以查看更多使用方法）
step 2: 寻找 SA coordinates
如果是pair-end 数据（leftRead.fastq和rightRead.fastq）两个文件分别处理
bwa aln reference.fa leftRead.fastq > leftRead.sai
bwa aln reference.fa rightRead.fastq > rightRead.sai
bwa aln reference.fa singleRead.fastq > singleRead.sai
如果希望多线程运行，在其中加入 -t这个参数，另外-f这个参数可以指定结果输出文件，如:
bwa aln -c -t 3 -f leftreads.sai reference.fa leftreads.fastq
step 3:转换SA coordinates输出为sam
如果是pair-end数据
bwa sampe -f pair-end.sam reference.fa leftRead.sai rightRead.sai leftRead.fastq rightread.fastq
如果是single reads数据
bwa samse -f single.sam reference.fa single.sai single.fastq
https://www.jianshu.com/p/859c0345624c
bwa mem [options] <idxbase> <in1.fq> [in2.fq]
bwa mem -t 4 -R'@RG\tID:foo_lane\tPL:illumina\tLB:library\tSM:sample_name'/path/to/human.fasta read_1.fq.gz read_2.fq.gz > sample_name.sam
-t，线程数，我们在这里使用4个线程；-R 接的是 Read Group的字符串信息，这是一个非常重要的信息 ，以@RG开头，它是用来将比对的read进行分组的。不同的组之间测序过程被认为是相互独立的，这个信息对于我们后续对比对数据进行错误率分析和Mark plicate时非常重要。在Read Group中，有如下几个信息非常重要：
(1) ID，这是Read Group的分组ID，一般设置为测序的lane ID（不同lane之间的测序过程认为是独立的），下机数据中我们都能看到这个信息的，一般都是包含在fastq的文件名中；
(2) PL， 指的是所用的测序平台，这个信息不要随便写！ 特别是当我们需要使用GATK进行后续分析的时候，更是如此！这是一个很多新手都容易忽视的一个地方，在GATK中，PL只允许被设置为：ILLUMINA，SLX，SOLEXA，SOLID，454，LS454，COMPLETE，PACBIO，IONTORRENT，CAPILLARY，HELICOS或UNKNOWN这几个信息。基本上就是目前市场上存在着的测序平台，当然，如果实在不知道，那么必须设置为UNKNOWN，名字方面不区分大小写。如果你在分析的时候这里没设置正确，那么在后续使用GATK过程中可能会碰到类似如下的错误。
(3) SM，样本ID，同样非常重要，有时候我们测序的数据比较多的时候，那么可能会分成多个不同的lane分布测出来，这个时候SM名字就是可以用于区分这些样本。
(4) LB，测序文库的名字，这个重要性稍微低一些，主要也是为了协助区分不同的group而存在。文库名字一般可以在下机的fq文件名中找到，如果上面的lane ID足够用于区分的话，也可以不用设置LB；
除了以上这四个之外，还可以自定义添加其他的信息，不过如无特殊的需要，对于序列比对而言，这4个就足够了。这些信息设置好之后， 在RG字符串中要用制表符（\t）将它们分开 。
sam转换bam（sam特殊二进制）
bwa mem -t 4 -R'@RG\tID:foo_lane\tPL:illumina\tLB:library\tSM:sample_name'/path/to/human.fasta read_1.fq.gz read_2.fq.gz | samtools view -S -b - > sample_name.bam
time$bwamem -t 40 -M -Y -R"@RG\tID:$RGID\tPL:ILLUMINA\tSM:$sample"$reference\$outdir/cleanfq/${fq_file_name}.paired.1.fq.gz$outdir/cleanfq/${fq_file_name}.paired.2.fq.gz |$samtoolsview -Sb - >$outdir/bwa/${sample}.bam && \echo"** BWA MEM done **"&& \
-M 将 shorter split hits 标记为次优，以兼容 Picard’s markDuplicates 软件。
-Y Use soft clipping CIGAR operation for supplementary alignments. By default, BWA-MEM uses soft clipping for the primary alignment and hard clipping for supplementary alignments.
链接：https://www.jianshu.com/p/d6cc153be28d
设置权限 chmod 777 ./*.sh
运行
以上，我们就完成了read比对的步骤。接下来是排序：
-@，用于设定排序时的线程数；-m，每个线程排序时最大的内存消耗；-O 指定输出为bam格式；-o 是输出文件的名字.
在排序完成之后我们就可以开始执行去除重复（准确来说是 去除PCR重复序列 ）的步骤了。
把参数REMOVE_DUPLICATES设置为ture，那么重复序列就被删除掉，不会在结果文件中留存。我比较建议使用第一种做法，只是标记出来，并留存这些序列，以便在你需要的时候还可以对其做分析。
这一步完成之后，我们需要为sample_name.sorted.markp.bam创建索引文件，它的作用能够让我们可以随机访问这个文件中的任意位置，而且后面的“局部重比对”步骤也要求这个BAM文件一定要有索引，命令如下：
$ samtools index sample_name.sorted.markp.bam
接下来是局部区域重比对，通常也叫Indel局部区域重比对。有时在进行这一步骤之前还有一个merge的操作，将同个样本的所有比对结果合并成唯一一个大的BAM文件【注】，merge的例子如下：
$ samtools merge <out.bam> <in1.bam> [<in2.bam> ... <inN.bam>]
【注意】之所以会有这种情况，是因为有些样本测得非常深，其测序结果需要经过多次测序（或者分布在多个不同的测序lane中）才全部获得，这个时候我们一般会先分别进行比对并去除重复序列后再使用samtools进行合并。