Featheast Lee 李羽东

1. BLAST是一种局部比对的搜索工具，采用了Heuristic方法。包括BLASTN, BLAST2, BLASTP, PSI-BLAST, TBLASTN…..
BLAST找到潜在匹配的种子：数据库索引话，将长度为W的字符拼版话，在数据库中寻找匹配(DNA-完全匹配，蛋白质-找到比阈值高的）；扩展潜在匹配；评估潜在匹配；检测和评估最后的匹配：利用Smith-Waterman局部比对算法，决定匹配的数据重要性

2. 低复杂区域：
基因组中包括低复杂区域，如重复的小片段（引物），高A-T区域（或其他有线的碱基），这些区域的匹配通常不明显，最好能在进行BLAST处理前屏蔽掉。
SEG：一种检测低信息区域的算法，利用信息理论，参数决定了粒度和力度。
1）检测低复杂区域，2）局部优化，尖锐边界

3. BLAST输出分数
S：DPA查询分数
Z：随机化查询序列多次，利用不同的比对
P：一个或多个序列的分数>=S的几率，p可以通过z计算出来
E：期望的序列分数>=S的数目，E=P*数据库的大小

4. Dotplots
比较两个序列，滑动窗口W，阈值T，比较窗口内的字符，计算窗口内的匹配数目，如果数目大于阈值则加上一个点

5. 多序列比对
打分方法：SP-成对数目，一致性（星形）：一个序列是其他序列的祖先，信息理论：最小熵，树形（渐进比对），图形

1. DNA, RNA和蛋白质序列都可以被看作为字符串，字符串的搜索算法有：Horspool/Boyer-Moore. KMP, Rabin-Karp, Suffix-trees。和生物学有关的方面包括：近似匹配，因为测序错误或者进化（在物种内部或之间）。我们需要寻找的是相似的字符串，部分匹配，能够达到近似的测量值。

2. 测量两个序列之间的距离：Euclidean距离，City Block距离，Hanmming距离
Edit距离是最小的操作数目来吧一个字符串转换为另一个字符串，操作包括插入/删除，和替换
优点：对生物进化的建模，考虑了序列相关的可能性；缺点：可能与实际的进化过程不符合，通常情况下两个相关的DNA片段是继承自同一祖先，而不是相互。

3. 序列比对
全局比对：插入空格，在中间或者序列1和序列2的结尾；将一个序列放在另一个序列的上方，使得每个字符都是另一个字符对应的或者是空格。
DPA算法：动态编程来计算出比对的最小值，两步：计算通过递归关系得到距离，回溯。
代表算法：Needleman-Wunsch算法
局部比对，代表算法：Smith-Waterman算法

困难：
RNA拼接：基因内区和外显子
开始和结束信号
非翻译区域：5UTR,3UTR
控制信号
结构化DNA
重复的区域，基因和伪基因
DNA包装影响基因表达

人类基因组：约有3*10pow9个碱基对

基因组VS后基因组时期：
2001年之前属于基因组时期：大多数的目标是测序
2001年之后属于后基因组时期：重要的目标包括分析和更有效的测序

DNA测序：传统和现代方法
传统：Sanger方法
工作流为：提纯基因组片段，扩大增强片段，测序片段，集合片段（集合片段是最难的部分）
将DNA片段裂解为单股，
现代：454方法，Shendure and Hanlee方法

下一代测序方法：
综合测序包括许多成像，需要耗费很多时间，数据管理问题，昂贵的原始数据归档费用，一般很难完成
对读取长度很小的算法需要花费相当的计算来集合

在基因组测序中的基本问题：
只能测序小片段，重复部分很困难，数据中有错误
问题1：大小分别
人类的基因组总数为3*10pow9个碱基，而Sanger方法只能测序500-1000碱基，下一代测序方法让不同更为明显，454测序只能250个碱基而其他的只能25-40个碱基
基因集成方法：层次集合，Shotgun测序
问题2：重复区域
30%的人类基因组是重复的，重复使得集成十分困难，散布的重复：SINES和LINES，串联重复
重复是近似的
问题3：错误
湿实验室更容易造成错误，如果序列的比较是近似的，它是重复区域？还是实验室错误？处理中的错误。

集成中的算法考虑：
错误，重复，准确估计，方向，覆盖率，不同片段的连接，效率

生物信息学的话题概述：
1） 大分子信息
2） 基因组的组织和表达
3） 基因组信息（数据库）的获得
4） DNA序列，结构，分析
5） RNA序列，结构，分析
6） 蛋白质和蛋白质家族

从计算机科学的角度，DNA是一个由4个字符组成的字符串，ACTGGTCAA……
DNA的基础：
ACGT四种碱基，A-Adenine腺嘌呤，C-Cytosine胞嘧啶，G-Guanine鸟嘌呤，T-Thymine胸腺嘧啶，是一种含氮的环状结构。
核苷是由碱基加上糖组成，糖分为脱氧核糖deoxyrubose和核糖ribose两种，前者出现在DNA中，后者出现在RNA中。
核苷酸是由核苷加上磷酸盐组成。
在RNA中，胸腺嘧啶T被尿苷Uridine取代。
DNA是一种双螺旋结构：
嘧啶Pyrimidines：较小，包括T和C， 嘌呤Purines：较大，包括A和G
两两配对，A-T(2根氢键，较弱），G-c(3根氢键，较强）

命名系统Nomenclature:扩展的核苷酸字符
单核苷酸:{A},{C},{G},{T}
任何：N={A,C,G,T}
嘌呤，嘧啶：Y={C,T}, R={A,G}
弱键/强键：W={A,T}, R={C,G}
氨基Amino/酮类keto：M={A,C}, K={G,T}
V={A,C,G}, H={A,C,T}, D={A,G,T}, B={C,G,T}
标准的序列如：TTAAACNGCSNTTT
字符表的大小为2pow4-1=15

DNA结构:
主结构：序列型，有方向的
次结构：沃森-克里克Watson-Crick双螺旋模型
高阶结构：三维超螺旋结构

DNA信息流，DNA是蓝图，蛋白质负责工作
DNA->RNA 转录, RNA->Protein 翻译
每一部都有预处理，还包括一些控制：
蛋白质控制：催化剂，抑制剂，调制器
级串联，暂时控制等等

基因和蛋白质：
基因是一系列的DNA用来编码蛋白质的，蛋白质做了大部分细胞内的工作
一个蛋白质内有3个DNA碱基
基因组有很多基因（已经被解码的），还有很多没有被翻译的片段

DNA信息：
DNA是蓝图，人类的DNA大约有3*10pow9个碱基，大部分(>90%)还没有被编码，大部分的 DNA(>30%)是重复的，展开大概有1米厂，组成部分随着不同的器官和物种而不同。

压缩：
压缩是一种将信息尽量精炼的办法。它包括：模型和方法。有些时候模型是十分有用的，即使没有编码。无损耗的压缩支持精确的原始序列还原。

模型和熵：
DNA的模型包括：
E.coli: p(T) = p(C) = p(A) = p(G) = 0.25, G+C=50%, 每一种碱基都是同等可能性
P.falciparum: p(A) = p(T) = 0.4, p(C) = p(G) = 0.1, G+C = 20%，不等的碱基比例，信息量小
信息理论允许我们测量混乱和不确定性的程度
熵是用来测量信息的：H=- <!– /* Font Definitions */ @font-face {font-family:宋体; panose-1:2 1 6 0 3 1 1 1 1 1; mso-font-alt:SimSun; mso-font-charset:134; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:3 135135232 16 0 262145 0;} @font-face {font-family:”Cambria Math”; panose-1:2 4 5 3 5 4 6 3 2 4; mso-font-charset:0; mso-generic-font-family:roman; mso-font-pitch:variable; mso-font-signature:-1610611985 1107304683 0 0 159 0;} @font-face {font-family:Calibri; panose-1:2 15 5 2 2 2 4 3 2 4; mso-font-charset:0; mso-generic-font-family:swiss; mso-font-pitch:variable; mso-font-signature:-1610611985 1073750139 0 0 159 0;} @font-face {font-family:”\@宋体”; panose-1:2 1 6 0 3 1 1 1 1 1; mso-font-charset:134; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:3 135135232 16 0 262145 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-unhide:no; mso-style-qformat:yes; mso-style-parent:”"; margin:0cm; margin-bottom:.0001pt; text-align:justify; text-justify:inter-ideograph; mso-pagination:none; font-size:10.5pt; mso-bidi-font-size:11.0pt; font-family:”Calibri”,”sans-serif”; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:宋体; mso-fareast-theme-font:minor-fareast; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:”Times New Roman”; mso-bidi-theme-font:minor-bidi; mso-font-kerning:1.0pt;} .MsoChpDefault {mso-style-type:export-only; mso-default-props:yes; mso-bidi-font-family:”Times New Roman”; mso-bidi-theme-font:minor-bidi;} .MsoPapDefault {mso-style-type:export-only; text-align:justify; text-justify:inter-ideograph;} /* Page Definitions */ @page {mso-page-border-surround-header:no; mso-page-border-surround-footer:no;} @page Section1 {size:595.3pt 841.9pt; margin:72.0pt 90.0pt 72.0pt 90.0pt; mso-header-margin:42.55pt; mso-footer-margin:49.6pt; mso-paper-source:0; layout-grid:15.6pt;} div.Section1 {page:Section1;} –>

∑i(Pi * log2pi)，当所有的概率均等的时候H的值最大，也就意味着不知道接下来会发生什么。
H(E.coli) = 2.0, H(P.falciparum) = 1.7

编码：常见的三种方法Huffman编码，LZ编码和Arithemetic编码。
1）Huffman编码：
静态编码，利用树的模型，每一个符号都是一个单独的树叶，将最小可能性的两个树叶合并，形成树，然后在剩下的节点中再选择，反复，直到树中的所有节点都是叶子为止。用0表示左，1表示右来区分路径。
缺点：需要给每一个节点赋值，当可能性是2的整数倍时比较好

2) Arithmetic压缩编码
允许存在部分的位，压缩类似于entropy，很难更好

3）LZ编码
适应性的，储存了前面可见字符的移动窗口，当重复足够长的时候指向原来的复件，节省了子字符串的输出成本。
缺点：最小的重复长度来完成压缩可能比模体还要大，在生物中，大部分的重复是近似的，需要更复杂的模型来表示重复。
用处：平均位数和基数在重复区域会下降-因为表示了更少的信息

信息理论在基因组学中：
DNA是由一串字符组成
压缩率（熵）测量的一串字符中的信息
用来：定位重复/相似的序列，相关的基因，相同器官或者伪基因
在比较序列前过滤掉低信息区域
从不同器官中提取DNA
在DNA中找到不同的区域

序列，结构和方法：
所有的大分子都包括序列，结构和方法
生物信息学的很重要的一部分就是找到以上三者之间的联系，从一个预测另外一个，发现关系，接口数据库

RNA结构：
主结构：序列，次结构：2维，第三结构：3维

蛋白质结构:
主结构：序列，次结构：双螺旋，片状，环状，第三结构：3维