最近在搞16S，发现了一个实践算法的最佳机会。

见文章：

文章利用了贝叶斯模型，调用了blast和muscle来对OTU进行taxonomy assignment。

可以看一下源代码，非常简单。

如果你能彻底理解本文的算法，并能看懂其源码，那你基本就打到了生信算法入门的水平。

说不定以后你也能随手发一个算法的文章哦！

---

BLAST

Query id

Subject id

% identity

alignment length

mismatches

gap openings

q. start

q. end

s. start

s. end

e-value

bit score

这几个名词必须理解深刻！

Sequence identity is the amount of characters which match exactly between two different sequences. Hereby, gaps are not counted and the measurement is relational to the shorter of the two sequences. This has the effect that sequence identity is not transitive, i.e. if sequence A=B and B=C then A is not necessarily equal C (in terms of the identity distance measure) :

A: AAGGCTT

B: AAGGC

C:AAGGCAT

Here identity(A,B)=100% (5 identical nucleotides / min(length(A),length(B))).

Identity(B,C)=100%, but identity(A,C)=85% ((6 identical nucleotides / 7)).

Similarity is the degree of resemblance between two sequences when they are compared. This is dependent on their identity. It shows the extent to which residues in aligned. Similar sequences have similar properties.

Sequence similarity is first of all a general description of a relationship but nevertheless its more or less common practice to define similarity as an optimal matching problem (for sequence alignments or unless defined otherwise). Hereby, the optimal matching algorithm finds the minimal number of edit operations (inserts, deletes, and substitutions) in order to align one sequence to the other sequence . Using this, the percentage sequence similarity of the examples above are sim(A,B)=60%, sim(B,C)=60%, sim(A,C)=86% .

The bit score gives an indication of how good the alignment is; the higher the score, the better the alignment. In general terms, this score is calculated from a formula that takes into account the alignment of similar or identical residues, as well as any gaps introduced to align the sequences.