专业背景：计算机科学 研究方向与兴趣: JavaEE-Web软件开发, 生物信息学, 数据挖掘与机器学习, 智能信息系统 目前工作: 基因组, 转录组, NGS高通量数据分析, 生物数据挖掘, 植物系统发育和比较进化基因组学
http://biohjanime.blog.sohu.com/113037416.html
http://baohua100.blog.sohu.com
近两个月，Genome Research 和 Bioinformatics期刊出了很多关于Solexa测序仪下，短序列的map和拼接算法和程序，基本原理还是indexing，exactly match, extend,decision， 加进去一些solexa测序的特有性质用以提高map质量，比如考虑测序质量分数。
不过目前的程序都是仅仅能处理map 基因组随机打断测得的短序列，而在处理transcriptome随机打断测得的序列方面会漏掉一些序列，因为这种情况下，有 少部分序列是 间断map到基因组两个甚至三个位置上的（由于内含子的原因），而现有的程序都是只考虑了35bp的reads完全连续的map搭配基因组上面（正式基因组打碎的情况）。 目前我正在做这方面改进，transcriptome solexa 测序下的 依据基因组的 map 和 拼接程序。
有三点可以改进而提高质量：
1.所有的reads除了map基因组外，还map一遍cDNA（如果该物种有cDNA数据的话），这样可以找到一些连续map到cDNA上面的，而不是连续map到基因组的 reads。
2.没有cDNA的情况下，可以做Gapped-Alignment，不过性能很差。或者把seed设小，像blast，如果一个read的不同区域map到基因组不同位置，而相隔距离又不超过某个阙值（一个内含子的长度），并且符合GT-AG规则，就可以判断为一条可信的map。
3.既然要尽量找到那些断裂的map，而35bp又很短，段成两节的话，太短，我们可以先cluster 这些reads，就是先根据reads间和map的结果，把reads 拼接长一点，在map 就有点像est map 了。
下面总结算法：
1.生成k-mer seed的indexing table ，这个索引表可以基于基因组序列或者reads集合序列，如果基于基因组的话，seed size取12bp的话，就是建立一张4的12次方 行的 table， 其中每行代表任何一种12bp长的序列，并且记录了该12bp序列在基因组上的位置。 数据结构采用 数组+链表。
2.扫描reads集合， （如果前一步建立了reads indexing table， 这一步就扫描基因组），每12bp扫描，直接在上一步建立好的indexing table中查找，找到reads中的对应与基因组上的位置。
3.延伸-判断，根据上一步map的情况，延伸，如果延伸到35bp，其中mismatch少于 所规定的参数（一般为3），就认为是一个好的map， 而丢弃那些 map 到 多个地方的 reads。
4.(有cDNA数据) map cDNA， 把上一步 map到多个地方或者map到一个地方但是延伸的时候mismatch超过标准的 reads 拿来做 cDNA的map。
4.1（无cDNA数据）Gapped-Alignment， 把上一步 map到多个地方或者map到一个地方但是延伸的时候mismatch超过标准的 reads 拿来做 Gapped-Alignment
4. 2 (无cDNA数据） reads 的 cluster ，根据reads间的信息，和已有map结果，做cluster，用以进一步优化 步骤4.1（无cDNA数据）情况下的 断裂map
5.合并3，4 的结果。
评论