《代码之美》（十三）－－基因排序器的设计

Jim Kent

人类基因组是一组数字密码,它通过特殊的方式包含了人体所需的所有信息. 这些信息存储在30亿个DNA碱基中.每一个碱基可以是A,C,G或T, 这样每个碱基有两比特的信息, 而人类基因组共有750M的信息. 通过许多基因组的进化分析, 那750M的信息里只有大约10%是真正需要的. 其他的90%都是进化的遗迹.

基因排序器帮助科学家从人类基因组的大约25000种基因中进行快速的筛选, 找出那些跟他们研究的课题关系最密切的信息. 

基因排序器是一个CGI脚本, 当用户用Web浏览器打开基因排序器的URL()时, Web服务器执行脚本并通过网络回送结果. 脚本的输出是一个HTML表单. 当用户点击表单中的按钮后,Web浏览器就发送一个URL给Web服务器,其中包含了需要过查找, 过滤的信息. 这些信息以值键对(variable=value)的形式传给服务器, 接着服务器再次执行脚本, 根据值键对产生一个新的HTML表单作为响应.

CGI脚本可以用任何语言编写, 基因排序器脚本实际上是一个用C语言编写的较大规模的程序. 与桌面系统中其他一些用户交互式的程序相比, CGI脚本可移植性较高, 但是它的交互性很一般--除非采用javascript(从而直接引入严重的可移植性问题),否则只有在用户点击一个按钮,然后花上一两秒钟等到一个新的 Web页面之后,都会显示更新. 话说回来,对于大多数基因应用程序的需要而言, CGI提供了可接受的交互性,以及一个非常标准的用户界面.

之前提到用户通过传键值对给CGI脚本来说明自己需要的信息. CGI的生命周期很短,所以不能通过程序变量来长时间保存信息. 但基因排序器需要在用户浏览好多个页面后仍然记住用户的需求. CGI提供了两种机制用于保存表单控件的不可见数据. 第一种是隐藏的CGI变量,数据通过类型为"隐藏"(hidden)的标签保存在HTML中; 另一种是cookie, 数据被浏览器保存并通过HTTP头传送.

Cookie可以长期保存数据,长到以年为单位, 而隐藏变量在Web页被关闭时就马上消失了. 另一方面, Cookie技术在最初发布时就引发了很多争议,而且一些用户还会在浏览器中禁止它. 大体上讲, Cookie和隐藏变量都不能保存大量的数据, 尝试通过这些机制保存4KB以上的数据都是不安全的.

为了综合利用cookie和隐藏变量的能力, 基因排序器使用一个叫"行李车"(cart)的对象通过SQL数据库将cookie和隐藏变量结合起来. 行李车维护两张数据表, 一张关联用户, 另一张关联Web会话(session). 两张表格式完全相同, 都有一个主键列, 一个包含通过URL传送的键值对的blob字段, 以及一个跟踪使用时间和访问计数的字段.

cookie中保存一个指向用户表数据的主键, 而隐藏的CGI变量中保存指向会话表数据的主键. 在启动时,先从cookie中得到用户主键, 如果有的话, 便根据这个主键找到用户表里的键值对并载入到哈希表中, 如果cookie中找不到主键的话,就产生一个新的用户主键,同时不载入任何值到哈希表里. 接下下, 脚本根据会话主键将会话表里的键值对载入到哈希表中. 如果存在同名的从用户表中载入的变量则覆盖它. 之后程序运行时便可以读写哈希表中的变量了.

当脚本退出时,会根据行李车当前内容更新数据库表. 如果用户禁止了cookie, 会话期间变量的信息仍然可以较长时间地保存. 会话跟用户主键分开也使得用户可以在两个独立的窗口中运行基因排序器而互不影响. 用户级的行李车使基因排序器可以从它上次被保存的地方继续运行, 即使用户在中间访问过另外一个网址也没关系.

CGI脚本中使用C语言构造了一个表示列(column)的多态对象:

struct column
{
    /* 数据 */
    struct column *next; /* 链表中的下一列 */
    char *name; /* 列名,用户看不到 */
    char *shortLabel; /* 列标签 */
    char *longLabel; /* 列描述 */

    /* 方法 */
    /* 在HTML中打印该列的一个单元格 */
    void (*cellPrint)(struct column *col, struct genePos *gp, struct sqlConnection *conn);
    /* 在标签行中打印标签 */
    void (*labelPrint)(struct column *col);
    /* 打印高级过滤器中的控件标签 */
    void (*filterControls)(struct column *col, struct sqlConnection *conn);
    /* 返回高级过滤器的位置列表 */
    struct genePos *(*advFilter)(struct column *col, struct sqlConnection *conn);

    /*　下面几个字段是查找表使用的　*/
    char *table;　/*　关联表(associated　table)的名字　*/
    char *keyField;　/*　关联表中的ＧenuId的字段　*/
    char *valField;　/* 关联表中的Value字段 */

    /* 除了跟查找相关的字段,关联表还使用如下字段 */
    char *queryFull; /* 返回两列键/值的查寻 */
    char *queryOne; /* 给定键,返回相关值的查询 */
    char *invQueryOne; /* 给定值,返回相关键的查询 */
};

上面的结构体中通过函数指针来实现多态方法.

名为columnDb,ra的文件包含了列的元数据。下面是这个文件一些片段：

name proteinName
shortLabel UniProt
longLabel UniProt (SwissProt/TrEMBL) Protein Display ID
priority 2.1
visibility off
type association kgXref
queryFull select kgID, spDisplayID from kgXref
queryOne select spDisplayId,spID from kgXref where kgID = '%s'
invQueryOne select kgID from kgXref where spDisplayId = '%s'
search fuzzy
itemUrl %s

name proteinAcc
shortLabel UniProt Acc
longLabel UniProt (SwissProt/TrEMBL) Protein Accession
priority 2.15
visibility off
type lookup kgXref kgID spID
search exact
itemUrl %s

name refSeq
shortLabel RefSeq
longLabel NCBI RefSeq Gene Accession
priority 2.2
visibility off
type lookup knownToRefSeq name value
search exact
itemUrl
fcgi?cmd=Search&db=Nucleotide&term=%s&doptcmdl=GenBank&tool=genome.ucsc.edu

上面的片段包含了三个列。工厂方法基于这个ra文件的信息来创建前述的列的Ｃ对象。ra这个扩展名的意思是“关系型替品”（relational alternative），因为它可以作为关系型数据库的替代品。因为有大量的实用工具，还是使用关系型数据库而非ra文件来保存数据，但由于ra文件的 读写解析都很容易，因此它们在应用程序中也被继续使用。columnDb.ra文件的内容被编排成三层目录结构。根目录是所有物种中都会出现的列的信息。 中间层的目录包含特定物种的信息。最底层的目录包含特定我和中DNA次序的不同集合的信息。

读取columnDb文件会得到一个元素为哈希表的哈希表。外层哈希表的键是列名，内层哈希表的键是字段名。从上面的ra文件片段可以看到，不同的列有不 同的类型（type）：查找（lookup）类型的列引用一个表，根据gene ID可以在这张表里得到最多一行的记录。ra文件中表示类型的行分别包含表、gene ID字段和列中显示的字段。关联（association）类型可以为单一的基因取得多个值，这些值会被显示成逗号分隔的列表。此外还有其它类型，比如基 因表达（gene expression）列，显示成多个彩色方块来表示基因在各器官中的数目。红色表示高于平均值，绿色表示低于平均值，黑色表示平均值。

过滤器可以应用到任何一列基因，从而显示只跟特定用途有关和基因。比如使用基因表达列过滤器和基因组位置过滤器可以查找大脑的Ｘ染色体上的基因。程序启动 时，到行李车中查找是否有过滤器，如果有，则把每一个列都过滤一遍。多个过滤器被排列成一个链，所有的过滤的结果进入下一次的过滤过程。最后通过所有过滤 的基因被放入一个以gene ID为键的哈希表，再把结果拷贝到输出中。

下面是一个处理通配符的列（关联类型）的过滤方法：

/* 过滤匹配通配符列表中任何一项的关联 */
static struct genePos *wildAssociationFilter(
    struct slName *wildList, boolean orLogic, struct column *col,
    struct sqlConnection*conn, struct genePos *list)
{
    /* 将关联按gene ID分组 */
    struct assocGroup *ag = assocGroupNew(16);
    struct sqlResult *sr = sqlGetResult(conn,  col->queryFull);
    char **row;
    while ((row = sqlNextRow(sr)) != NULL)
        assocGroupAdd(ag, row[0], row[1];

    /* 寻找匹配的关联并把它们放进passHash表中 */
    struct hash *passHash = newHash(16);
    struct genePos *gp;
    for (gp = list; gp != NULL; gp = gp->next)
    {
        char *key = (col->protKey ? gp->protein : gp->name);
        struct assocList *al = hashFindVal(ag->listHash, key);
        if (al != NULL)
        {
            if (wildMatchRefs(wildList, al->list, orLogic))
                hashAdd(passHash, gp->name, gp);
        }
    }
    /* 创建经过过滤的列表，善后清理，返回 */
    list = weedUnlessInHash(list, passHash);
    hashFree(&passHash);
    assocGroupFree(&ag);
    return list;
}

Jim认为基因排序器的代码漂亮在于：行李车系统使得通过Ｗeb构建交互式程序变得相对容易，即使它使用CGI接口；虽然排序器用C语言写的，列的代码却 是基于支持多态的对象设计的；这样的设计使列的添加只需编程简单的文本（ra）文件，同时将磁盘寻道将至最低，毕竟磁盘寻道是当前计算机系统的性能瓶颈。

：1983年开始了自己 的职业生涯，主要从事绘画和动画软件的开发。他开发了Aegis Animator、Cyber Paint以及Autodesk Animator等获奖软件。1985年成立公司Dancing Flame。他在2002年获得生物学博士学位。在2000年攻读博士学位的同时，还开发出GigAssembler，计算出了第一批人类基因组。