2012年寒假读书笔记

Posted on by
3

假期，难得的假期。虽然依然要写文档，依然要写代码，但还是看了几本书。

《黄瓜的黄,西瓜的西》：在美国单口相声界打拼得颇有成就的华人，黄西的简单自传。黄西同学生化背景，搞过Bioinformatics，在休斯敦呆了几年，去过Galveston，申请过致病基因的专利，很多东西看着很亲切。至于书的水平，恩，跟他的笑话还有差距。

《银河系搭车客指南》：其实就是大名鼎鼎的《银河系漫游者指南》。在我看来是荒诞科幻的代表作啊，作者的想象力实在是太天马行空了。书的影响力也是巨大的，比如在Google里面搜索“the answer to life the universe and everything”，会看到Google的第一个搜索结果是42。为什么是42？看看这本书就知道了。BTW，书比电影好看。

《时间中的侦探》：在豆瓣上看到了如潮的好评，看完之后感觉如此而已。其实内核跟电影《源代码》差不多，只是更简单些。值得一看，评价一般。

《美国种族简史》：老罗推荐的一本书。确实不错，讲述各个种族在美国的发展史，心酸泪水和成功。一个种族的成功不是偶然的。

《Essential C++中文版》：我承认我的C++水平很烂，我恶补还不行吗？呵呵，为了写代码，恶补一下C++知识。R、Perl之类的写得太多了，C和C++写起来都手生了。这本书算是C++ Primer的精简版，我实在是不想背那么厚的C++ Primer。除了专业名词跟我们的习惯不一样，侯捷老师对这本书的翻译还是很赞啊，学习。

开源二三事

Posted on by
4

ClusterViz最初是给本科毕业生的毕业设计题目，一个小师妹选了这个题目，最终做得不错。其实我一开始没想着本科生能做出来。不过这种项目的最终结果由于我长期以来对写论文的不感兴趣，只是小师妹发表了一篇中文论文。但最近在搜论文的时候，竟然发现，这个很长时间没有更新的Cytoscape插件的用户手册竟然被Plant Science上的论文引用了，还是橡树岭国家实验室和普林斯顿大学这样牛单位的论文。我发的那些垃圾论文还没人来引呢，这张一页纸的用户手册竟然有人引用。免费+开源的软件果然有吸引力啊。

另外一个事情还是关于Cytoscape的。很久以前开始着手翻译Cytoscape的用户手册，在Google Code上建了一个Cytoscape-cn的代码库。一份不完整的翻译件已经被下载了将近7000次，不包括其他网站的转发。更好的消息是，在我断断续续地独立工作这么久之后，收到FULXIE同学的邮件说要加入项目，贡献点力量。这不仅仅是多了一个人，也让我燃起了继续该项目的动力。我们应该能在Cytoscape 3.0发布之前发布一份2.X版本的完整用户手册。

最近GitHub很火，把最近做的表观遗传学数据分析的代码堆到了那个上面。因为数据比较大，为了效率，重新捡起了很久没写过的C++。如果老板和合作方没意见的话，就继续在上面堆代码。听说，现在招码农都得看GitHub的账号，得攒点记录啊，哈哈

2011年年终总结

Posted on by
11

这个博客上总共发过三篇“总结”，最近一次是2011年的年中总结，其中对今年下半年的目标是这样罗列的：

  1. 争取发表两篇论文
  2. 完成Android的书，写点跟R和生物信息有关的东西，放到豆瓣的新读书计划里面去。
  3. 继续生物信息数据分析技术的商业服务尝试
  4. 迎接小陈钢的到来
  5. 搬新家
  6. 想从VIM切换到Emacs算不算大事呢？反正我觉着是个挺大的事情

完成的情况如下：

  1. 两篇论文的目标在老板的帮助下算是完成了，也超过的学校对博士生毕业的要求。写代码的乐趣远大于写论文。
  2. Android的书没有翻译完，真的很对不起编辑，还得继续努力。R和生物信息的东西都断断续续地写了一些。
  3. 生物信息数据分析商业服务的尝试依然在继续，有痛苦，有成就，凡要做事，皆如此。
  4. 儿子的到来给家里带来很多乐趣，也让我感到了更多的责任。每天晚上看到老婆抱着孩子睡着，顿时觉得自己所有的付出都有了意义。
  5. 搬家顺利完成，虽然新房子的装修有种种遗憾，但第一次拥有自己的房子，感觉还是不错。好吧，我承认，这房子大部分属于中国建设银行。
  6. 从VIM迁移到Emacs没有完成。Emacs太博大精深了，实在不是一下子就能灵活运用的。一篇《Emacs入门笔记》在Wordpress的草稿箱里面攒了很久了。

下半年还有一些值得记录的情况：

  1. 参与了一个信息系统的建设工作，当甲方也非常的不爽。再次坚定了我远离行政工作的决心。
  2. 参加了两次会议，一次韩国，一次深圳，获益良多。
  3. 收到若干个团队的面谈邀请，跟其中两个团队见面，收到了一个感觉很不错的offer。
  4. 几乎从未在学校获奖的我，在老板的支持下得到了学院的学术奖一等奖。感谢老板，但也觉得受之有愧。

2012年，如果世界没毁灭，或者我拿到了船票的话，希望能实现下面的目标：

  1. 在上半年完成博士毕业答辩的工作，把title从Mr.换成Dr.
  2. 争取能加盟自己心仪的团队，完全融入新的工作环境。
  3. 在毕业前，参与并完成一本R语言书籍的翻译工作。
  4. 在毕业前，完成至少一项湘雅医学院的合作项目。
  5. 丰富家庭成员的生活，至少完成一次全家的长途旅行。
  6. 恶补算法方面的知识，读完至少一本纯生物的书

其实，对未来的一年做规划，实在是太难了。能规划好下个星期已属不易。只是非常不全面的罗列着自己的目标，希望2012年能有所长进。

Teverna 2入门笔记

Posted on by
1

在mail-list里面看到一个叫uGene的软件发布了新版本，摸索过去，发现已经有人将工作流的概念引入到生物数据的分析中。大赞！我接触到的生物数据分析的典型过程通常都是这样的：

  1. 收集数据
  2. 数据处理
  3. 数据分析
  4. 生成图表

如何将一项生物数据分析的工作标准化地描述，显然不太容易。收集数据的来源可能是从ftp/http下载，或者从各种web server获取，或者是原始的实验数据；数据处理可能涉及到二进制文件，通常会用到Perl、R等各种脚本；数据分析阶段为了快速的建立分析模型，R、Perl、Matlab等等都会出现，再加上现在数据量变大之后还会涉及到hadoop等分布式计算；图表的生成就更加五花八门了。文字描述很难严谨的描述这种过程，也能不能确保这个过程的可重复性。通常的做法是用shell或perl脚本把各种操作胶合在一起，但分析过程中参数的调整和记录之类的事情却变成了麻烦。如果能有一个很好的生物数据分析工作流引擎，将各种常见的操作分解成组件，同时允许用各种语言添加组件，实现便捷的流程设计，自动执行流程，并做好历史记录，无疑会成为当下各种生物信以息公司提升效率的利器啊。

搜索了一下，Teverna已经在某种程度上实现了这些功能。Teverna是Java编写的，有图形界面，也可以在命令行中执行工作流。默认可以通过R、Beanshell（还真有地方能用上这玩意）等脚本添加组件，可以通过运行外部命令实现对各种脚本的调用，可以访问各种标准的Web服务获取数据和分析结果。已经发展了很多年的项目了，只是我孤陋寡闻而已。文档丰富完整，社区还算活跃，有不少人分享自己设计的工作流。这种好东西，当然得拿来折腾一下。

Taverna界面

实现一个简单的流程：输入两个数字，然后在R中计算和，将写过写入指定的文件。设计好之后的流程图如下所示。

分析流程图

简单解释一下，红色向上箭头只的是整个流程的输入，即那两个数字。绿色向下箭头指的是整个流程的输出，这里是计算结果。中间就是各种操作，Rshell中是计算两数之和的R代码，Write_Text_File是一个写beanshell脚本。这些操作在Taverna中都被成为服务（service）。我定义的Rshell服务会接收两个参数，输出一个结果。Write_Text_File是自带的服务，接收三个参数：输出文件名称、输出文件内容和文件编码方式。在这个流程中，输出文件名称和文件编码方式都是用字符串常量定义的，文件内容来自RShell服务的输出结果。最后，计算的结果也会保存到sum中。感觉有点像是一个个的函数，一个接一个。

点击主界面上方的绿色箭头执行工作流，会提示出入流程输入参数，然后可以在流程图上直观地看到流程的执行进展。在Results中会有每次运行的记录。

微博上有朋友指出，Taverna的问题就是效率。现在还没体验到，过两天搞一个真正的分析流程上来试试。

BTW，这么多年了，关于Taverna的中文文章真少啊。

组合排列

Posted on by
Reply

继续厕所读书，Richard A. Brualdi的《组合数学》，第三章，排列与组合。

四个最基本的计数原理：

  • 加法原理：设集合S划分为S_1, S_2, S_3, \ldots , S_m。则S的元素个数等于每个部分的元素个数的总和，即：

        \[ \left | S \right | = \left | S_1 \right | + \left | S_2 \right | + \left | S_3 \right | + \ldots + \left | S_m \right | \]

  • 乘法原理：令S是元素的序偶(a, b)的集合，其中第一个元素a来自大小为p的集合，而对于a的每个选择，元素b都存在q中选择。于是，S的大小为p\times q:

        \[ \left | S \right | = p \times q \]

  • 减法原理：令A是一个集合，而U是包含A的更大的集合。设：

        \[ \bar{A} = {x \in U: x \not\in A} \]

    是A在U中的补。那么A中的元素个数|A|等于：

        \[ |A| = |U| - |\bar{A}| \]

  • 出发原理：令S是一个有限集，它由以下方式被划分出k部分，每一部分包含相同数目的n元素。此时，划分中的部分的元素个数等于：

        \[ k=\frac{|S|}{n} \]

都不记得当年学习排列组合时这些概念是怎么描述的了。接下来是普通的排列组合。

本章最后介绍的是之前没有了解过的多重集的排列组合。多重集，即含有重复元素的集合。这种集合实际上违反了笛卡尔法则，不过在解决一些实际的排列组合问题时很有用。

鸽巢原理

Posted on by
Reply

最近的厕所读物是很早之前从China-pub淘来的二手书，Richard A. Brualdi的《组合数学》（Introductory Combinatorics 4th ed）。这两天读到的是第二章，鸽巢原理，做点笔记。

鸽巢原理

鸽巢原理

1834年，德国人Johann Dirichlet将鸽巢原理（pigeonhole principle）形式化，并用于后来被称为Dirichlet近似理论的证明。所以鸽巢原理又被称为Dirchlet原理。Dirichlet是一朵奇葩，这里按下不表，有兴趣的可以去维基百科——Johann Dirichlet。

Dirichlet近似理论是这样的：

对于任意实数\alpha和正整数N，存在整数p、q，1 ≤ q ≤ N，使得：

    \[\left | q \alpha -p \right | \le \frac{1}{N+1}\]

简单来说，任何实数都可以通过线性变换逼近某个整数。

Dirichlet是在证明这个理论的过程中将鸽巢原理形式化了，或者可以说这是第一次正儿八经地表述和使用了鸽巢原理。来看看Dirichlet近似理论的证明(参考Dirichlet近似理论证明)。

不妨假设N \geq 2，对于(1, N]区间中的整数a，都有：

    \[ r_a = a\alpha - [a\alpha] \in [0,1) \]

其中[a\alpha]表示小于a\alpha的最大整数。这个是显然，任何一个实数减去其整数部分后剩下的小数部分显然是大于等于0，小于1的。因为存在N个整数a，加上0和1，所以在[0,1]这个区间内总共有N+2个数。N+2个数将[0,1]这个区间分割成了N+1个更小的区间。这些小区间中至少会有一个小区间的长度小于或等于\frac{1}{N+1}。这些小区间实际上就是两个数的差值，换言之就是在这N+2个数中至少有两个数之间的差值小于或等于\frac{1}{N+1}。

在长度小于等于\frac{1}{N+1}的这一对数中，如果其中一个数是0或1，那就是说存在a, b \in (1,N]：

    \[ \left | r_a - r_b \right| = \left | (a\alpha - [a\alpha]) - (b\alpha - [b\alpha])\right | \leq \frac{1}{N+1} \]

即：

    \[ \left | \alpha(a-b)-([a\alpha] - [b\alpha]) \right | \leq \frac{1}{N+1} \]

因为a和b是整数，所以a-b也是整数；同样，[a\alpha] - [b\alpha]也是整数。不妨假设q=a-b, p=[a\alpha] - [b\alpha]，则有：

    \[ \left | q \alpha - p \right | \leq \frac{1}{N+1} \]

证明完了。这里面什么地方用到了鸽巢原理？就是这句话：

N+2个数将[0,1]这个区间分割成了N+1个更小的区间。这些小区间中至少会有一个小区间的长度小于或等于\frac{1}{N+1}

鸽巢原理的一般形式是这样的：

令q_1, q_2, q_3, \ldots, q_n为正整数。如果将q_1 + q_2 + q_3 + \ldots + q_n -n + 1个物体放入n个盒子中，那么，或者第一个盒子至少有q_1个物体，或者第二个盒子至少有q_2，\ldtos，或者第n个盒子至少有q_n个物体。

用到Dirichlet近似理论证明中就是将N+2个数字放入N+1个区间中，其中至少有一个区间至少有两个物体。区间的长度是\frac{1}{N+1}，所以位于同一个区间中的两个数的差值就小于或等于\frac{1}{N+1}。

鸽巢原理是最基本的组合学原理。曾经在小学、中学上奥数班时了解过皮毛，现在再来回味一下还是很有意思的。

2011年韩国之旅[1]

Posted on by
1

太多的事情没有记录了，争取能补一下。

2011年8月8日到13日，在日本东京大学和韩国科技大学的资助下，到韩国大田市参加了AYRCOB（亚洲青年计算生物学和组学）2011会议。

8月8号晚上从黄花机场的新航站楼出发，东航的航班飞往首尔仁川机场。第一次在黄花机场坐国际航班，也是在新航站楼启用后第一次来机场。机场修得不错，规模也大了不少。但照现在的使用情况，估计用不了太久，新航站楼又会像老航站楼一样繁忙的。

四个来小时的飞行，外加一小时的时差，我大概在9号早上5点多抵达了仁川机场。下飞机，入境，溜哒，找地方上网。号称全球网速最快的国家，机场的免费无线网络的网速也是刚刚的啊。ipad更新应用的速度跟我朝完全不可同日而语，笔记本上下载文件也屡屡达到3~4MB/s的水平。从来没用过如此给力的*免费*网络。不过机场的卫生情况并不比国内好多少，可能是我到得太早了，清洁人员还没上班。处理邮件，闲逛一会，然后在候机大厅找了个长椅开始补觉——组委会安排的接机大巴要中午才到，自己掏钱坐大巴也得要等到上午9点多。

来几张首尔机场的照片。仁川机场若干年以来一直是全球机场联合会评出的全球最佳机场，这是奖牌。

View at Picasa
09-Aug-2011 04:24, OLYMPUS E-510, 3.5, 14.0mm, '0.125' sec, ISO 100

机场里面展示的混动版起亚K5。另外一侧还有混动版的现代第八代索纳塔。
View at Picasa
09-Aug-2011 04:25, OLYMPUS E-510, 4.5, 22.0mm, '0.125' sec, ISO 100

这是仁川机场里面用来表演节目的地方，到一定的时间就会有一人表演歌舞、魔术等节目。算是等飞机消磨时间的好地方。
View at Picasa
09-Aug-2011 04:24, OLYMPUS E-510, 3.5, 14.0mm, '0.125' sec, ISO 100

消磨时间到中午，在机场的一家饭店手舞足蹈地点了一份海鲜拌饭，够辣，味道不错，价格8500韩元，合约人民币60的样子，还能接受。只是分量对我来说不够啊。
View at Picasa
09-Aug-2011 11:28, OLYMPUS E-510, 3.5, 14.0mm, '0.04' sec, ISO 100

吃过海鲜拌饭，到指定地点跟来接机的韩国美女帅哥接头。确实是美女帅哥，穿着也比我职业多了，都是韩国延世大学的学生。上大巴，朝大田市出发。先到首尔市内的延世大学接了通行的延世大学学生，然后一路向南。从地图上看，大概由南向北穿过了四分之一个韩国。到达酒店Toyoko Inn的时候已经是日落时分了。注意，这里是Toyoko Inn，不是Tokyo Inn。我还一直以为是在韩国住“东京酒店”，原来是我看走眼了。

在酒店稍作休息，就跟新加坡来的Hwee Meng同学一起到外面寻觅吃的。先是绕着酒店所在的街区溜哒了一圈。当然，照片是少不了的。

谁说只有我朝的政府大楼才威武？这是大田市的是政府大楼，也很帅嘛。

View at Picasa
10-Aug-2011 17:32, OLYMPUS E-510, 5.0, 18.0mm, '0.003' sec, ISO 400

绕了一圈，最后杀进了路边的一家韩国烤肉店。盘腿坐下，老板娘送来一张菜单——全部是韩文。我们一脸茫然，手势+英语比划了一下，老板娘再次送来一张菜单——中、日、英全有，赞！不过这价格就实在是——韩国的肉真的很贵啊。我点了一份石锅拌饭，Hwee Meng同学点了一份什么牛肉汤，然后点了两份五花肉。不多说，上图。

View at Picasa
09-Aug-2011 18:07, OLYMPUS E-510, 3.5, 14.0mm, '0.125' sec, ISO 100

虽然我们只点了三个东西，但是上来的大小盘子硬是摆满了一桌了啊。对面的倩影就是正在拍照的Hwee Meng同学。

吃完后AA付款，我自己肉疼。稍作溜哒后各自回房间休息。

韩国之行的第一天结束。

最近博客更新少的原因

Posted on by
4

看了看博客的侧栏，10月份只更新了一篇东西，还是个有头没尾的翻译。原因？很简单，下面的图能说明一切。

孩子和孩子他妈

孩子和孩子他妈

他来了，所有的工作进度都受到剧烈的影响。

希望他健健康康快快乐乐的长大，然后在这个纷繁的世界上有一次属于自己的愉快旅程。

DNAnexus的考题[0]

Posted on by
Reply

最近生物信息领域最热门的公司无疑是从Google拿到投资并计划接管NCBI数据库的DNAnexus公司。有了钱，接下来自然就是招兵买马，要招的几乎全是计算背景的人。在其网页上给出了两个难题，说是如果解出了这两个题目，并且被DNAnexus聘用的话，会得到免费的全基因组测序服务。来看看第一个题目，翻译成中文，如下：

Danny Dendrite是DNAnexus的一位工程师的一个脑细胞。他的日子过得很滋润，每天都在思考各种有趣的问题，还能从办公室里的各种小吃获得滋养，不亦乐乎。不过，他也有自己的烦心事，关于DNA的：因为在细胞核中太多诸如蛋白质之类的其他物质，所以Danny Dendrite有时找不到地方放他的基因组。好在Danny Dendrite对其细胞核中的各种东西都有详细的记录。Danny Dendrite把他得细胞核表示成一个N纳米乘M纳米的网格，他知道其中的每一平方纳米是否被填充了东西。而且，他还知道他的基因组有X纳米长。现在要帮Danny Dendrite写个程序来管理他的细胞核，找到他的DNA。Danny Dendrite会给你一个这样子的文件：第一行是细胞核网格的行数（N）和列数（M），然后是他的基因组的长度（M）。接下来就是N行数据，每一行有M个字符：o表示空的，而x表示被填充了。

要从中帮Danny Dendrite找到一条由这个网格中的一串位置组成的路径，起点可以是细胞核中的任何位置，但这个路径要满足以下要求：

  • 每个位置都是空的；
  • 每个位置跟其前一个位置的距离都是1nm
  • 每个位置最多只经过一次
  • 经过的位置的总数等于Danny Dendrite的基因组的长度（包括起始位置）

如果不存在这样的路径，输出impossible即可。

接下来给了这样一个例子，输入文件：

5 4 8
oxoo
xoxo
ooxo
xooo
oxox

输出的路径可以是：

1,1
2,1
3,1
3,2
3,3
2,3
1,3
0,3

矩阵的行列都是从0开始标的。

最简单直接的思路是，根据题目的规则和数据文件，构建一个网络，然后判断网络中是否存在长度为X的路径。这不是个简单的问题，在参数计算理论中，通过color coding算法可以比较高效的解决这个问题。详情待续~

Android资源文件的大小限制及解决方案

Posted on by
Reply

一个应用调用自定义字体，在部分机器上无法正确使用自定义的字体。有些甚至是同一款机器，所以分辨率之类的因素可以排除。最后发现是版本原因，系统版本低于Android 2.3的机器上通通出问题，2.3以上的正常。但代码都是针对Android 1.6的API的啊，别说2.3，连2.0的API都没用到。查询Android 2.3的highlights，看到下面这句话：

There is no longer a limit on the size of compressed .apk assets that can be read.

从2.3开始，对可读取的压缩后的.apk中的资源的大小不再有限制。这意味着在2.3之前都是有限制的。翻看LogCat中的记录，会有如下的信息：

Data exceeds UNCOMPRESSE_DATA_MAX ( XXXXXXXXXX vs 1048576)

其中XXXXXXX是一个大于1048576的值。也就是说，在压缩打包到APK文件中的资源文件，在解压后的大小不能超过1MB。否则在Android 2.3之前的系统中就无法正确读取该资源文件。而我们用的中文字体文件的大小显然超过了1MB，失败的原因就在这里。怎么办？

中文社区中对此有这样的一篇广为转载的文章，《Asset限制文件大小UNCOMPRESS_DATA_MAX为1MB》，其中的结论是：

目前解决的方法只有将文件放入到sdcard，但这样除了microsd的读取IO效率和耗电量解决不是很好，同时sd卡移除时可能存在问题，解决的方法如果数据量大的化通过sqlite是一种解决方法，同时openFileOutput方式读取也是不错的选择，看来android操作系统中最安全控制的严格，但犯了一个不小的错误。

字体文件显然没办法塞到sqlite里面，要求所有的用户都有SD卡也不太友好。又翻到一篇相关的英文文章，Dealing with Asset Compression in Android Apps。从中可以看出，Android 2.3之前的版本只对压缩过的资源文件的原始大小做了限制，这种限制可能是出于计算性能的考虑。对于没有压缩的文件，是没有大小限制的。哪些文件不会压缩？图片、音频、视频，包括这些后缀：

“.jpg”, “.jpeg”, “.png”, “.gif”, “.wav”, “.mp2″, “.mp3″, “.ogg”, “.aac”, “.mpg”, “.mpeg”, “.mid”, “.midi”, “.smf”, “.jet”, “.rtttl”, “.imy”, “.xmf”, “.mp4″, “.m4a”, “.m4v”, “.3gp”, “.3gpp”, “.3g2″, “.3gpp2″, “.amr”, “.awb”, “.wma”, “.wmv”

从Android的源代码中可以知道，Android的打包工具是通过文件的后缀名来判断文件是否需要压缩的。如果文件的后缀名是上面这些后缀，文件就不会被压缩，大小也就没有限制；如果文件的后缀不是上面这些，就对其进行压缩，并且在Android 2.2上有1MB的大小限制。字体文件后缀通常是.ttf，属于要被压缩的，在Android 2.2之前的版本中就有了体积限制。不过，看到这里，解决方案也出来了，把字体文件的.ttf后缀改成上述任意一个后缀，然后修改相应的代码就可以。好猥琐的解决方案啊~~

结论：中文社区的水平似乎还是跟老外有点差距，或者是高手的分享意愿不强烈；Android本身及其相关的开发工具的源代码是值得去读读的；Android里面有一些看似奇怪的条条框框，这种非API的版本变化，如果不在2.3以下的机器上测试是根本发现不了的。