字符串匹配问题的基本形式是：在文本串 text 中，查找模式串 pattern 出现的位置。最朴素的做法是暴力匹配：一旦发生不匹配，就把模式串整体右移一位，重新从头比较。这种方法的问题在于：已经比较过的字符被重复比较, 最坏时间复杂度是 O(nm). KMP（Knuth–Morris–Pratt）算法的核心目标只有一个：当匹配失败时，模式串尽可能向右跳，而不是回到起点。

输入是两个字符串，输出是对齐后的两个字符串。

简介使用过pysam和samtools的小伙伴肯定了解 pileup的操作，如果把 BAM 文件看作表格的话，那么通常我们是按行去解析它的 record，进而获得一些信息，例如比对到哪条染色体，比对的开始位置和结束位置等. 另一种情况下，我们想要按照列去循环解析，得到这个列上的具体信息，典型的就是这个列上比对序列的碱基是什么？比对序列的位置是什么？以及是 Match or Mismatch or indel 等。那么，该操作就需要引入pileup操作了。

首先在 shell 中测试如下命令12#!/bin/shtime gzip -d -c risearch_chr1:143971112-143971134:+:FAM72C.out.gz > risearch_chr1:143971112-143971134:+:FAM72C.out

我们在运行 bwa mem 比对的时候，由于某些不明的原因会造成程序中断，例如内存超了，IO 错误，计算节点崩溃等，然而 BAM 是否完整很难察觉，最终导致后续流程无法运行。这里，我们通过一段简短的代码来检查 BAM 文件的完整性，代码如下：

如题，官方已经提供了一个 R 的版本createGCcontentFile.R ，但是根据代码就能看出这个版本非常占内存了，首先要把基因组整个序列都 load 入内存中去，每次计算出的矫正数据也是储存 dataframe 中。为了降低内存占用，也为了提高计算速度，我写了一个 julia 版本的。代码如下：

Julia 读取 BAM 的库想要计算Insert size，需要提供一个基因组比对后的文件，sam也好，bam也罢。那么，使用 julia 语言计算该值的第一步便是了解如何读取和解析BAM文件格式。

拆分原理 软件的逻辑是首先获取 barcode 列表。然后采用多线程分别在 fastq 文件中并行提取对应 barcode 的 reads。 WGS 的下机数据经常出现在 fastq2 里。所以程序会从 fastq 中自动查找是否存在对应 barcode。 程序可以自动检测 barcode 始于开始还是末尾，计算 hanming 距离，运行 1bp 的 mismatch。

众所周知，计算相关性非常的简单，因为R 语言中有函数cor.test(),该函数可以计算多种方法的相关性检验，返回相关性，Pvalue 等检验值，但是这个函数在Julia中并不存在，让 Julia 作为一门科学计算语言显得并不完美。

前言自己写的好几种算法企图实现 bedtools 的功能，虽然 julia 性能足够好，但都难以在效率上达到 bedtools 的性能，于是最后只能借助轮子了。