2023年10月10日发(作者：x疾病)

第２７卷第９期

２０１０年９月

计算机应用研究

Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ

Ｖ０１．２７ Ｎｏ．９

Ｓｅｐ．２０１０

基于ＣＵ ＤＡ的蛋白质翻译后修饰鉴定

ＭＳ・－Ａｌｉｇｎｍｅｎｔ 算法加速研究

翟艳堂 ，涂强 ，郎显宇 ，陆忠华 ，迟学斌

（１．中国科学院计算机网络信息中心超级计算中心，北京１００１９０；２．中国科学院研究生院，北京１０００４９）

摘要：对ＭＳ—Ａｌｉｇｎｍｅｎｔ算法进行分析得出该算法很难满足大规模数据对鉴定速度的要求，而且具有的一个特

点是相同的任务在不同的数据上重复计算，为数据划分提供了基础。基于ＣＵＤＡ编程模型使用图形处理器

（ＧＰＵ）对步骤数据库检索及候选肽段生成进行加速优化，设计了该步骤在单ＧＰＵ上的实现方法。测试结果表

明，此方法平均加速比为３０倍以上，效果良好，可以满足蛋白质翻译后修饰鉴定中大规模数据快速计算的需求。

关键词：蛋白质翻译后修饰鉴定；ＭＳ—Ａｌｉｇｎｍｅｎｔ；图形处理器；统一计算设备架构

中图分类号：ＴＰ３１２ 文献标志码：Ａ 文章编号：１００１—３６９５（２０１０）０９—３４０９ ０６

ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１—３６９５．２０１０．０９．０５６

Ｒｅｓｅａｒｃｈ ｏｆ ＣＵＤＡ．．ｂａｓｅｄ ａｃｃｅｌｅｒａｔｉｏｎ ｏｆ ＭＳ．．Ａｌｉｇｎｍｅｎｔ ｆｏｒ

ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ｏｆ ｐｏｓｔ—ｔｒａｎｓｌａｔｉｏｎａｌ ｍｏｄｉｉｃａｔｉｏｎｓ ｆ

ＺＨＡＩ Ｙａｎ—ｔａｎｇ ， ，ＴＵ Ｑｉａｎｇ ，ＬＡＮＧ Ｘｉａｎ—ｙｕ ，ＬＵ Ｚｈｏｎｇ—ｈｕａ ，ＣＨＩ Ｘｕｅ ｂｉｎ

（１．Ｓｕｐｅｒｃｏｍｐｕｔｉｎｇ Ｃｅｎｔｅｒ，Ｃｏｍｐｕｔｅｒ Ｎｅｔｗｏｒｋ Ｉｎｆｏｒｍａｔｉｏｎ Ｃｅｎｔｅｒ，Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆＳｃｉｅｎｃｅ，Ｂｅｉｊｉｎｇ １００１９０，Ｃｈｉｎａ；２．Ｇｒａｄｕａｔｅ Ｕｎｉｖｅｒｓｉｔｙ

ｆＣｈｉｎｅｓｅｏ Ａｃａｄｅｍｙ ｏｆＳｃｉｅｎｃｅ，Ｂｅｒｉｎｇ １０００４９，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｆｉｒｓｔｌｙ ａｎａｌｙｚｅｄ ＭＳ—Ａｌｉｇｎｍｅｎｔ．Ｉｔ ｃｏｕｌｄ ｎｏｔ ｗｅｌｌ ｍｅｅｔ ｔｈｅ ｃｈａｌｌｅｎｇｅ ｏｆ ｌａｒｇｅ ｓｃａｌｅ ｄａｔａ．Ｏｎｅ ｏｆ ｉｔｓ ｌｅａ—

ｔｕｒｅｓ ｗａｓ ｔｈｅ ｓａｍｅ ｃｏｍｐｕｔｉｎｇ ｏｐｅｒａｔｉｏｎｓ ｒｅｐｅａｔ ｏｎ ｄｉｆｆｅｒｅｎｔ ｄａｔａ．Ｔｈｉｓ ｆｅａｔｕｒｅ ｐｒｏｖｉｄｅｄ ｂａｓｅ ｆｏｒ ｄａｔａ ｐａｒｔｉｔｉｏｎ．Ｔｈｉｓ ｐａｐｅｒ ｔｈｅｎ

ｕｓｅｄ ＧＰＵ（ｇｒａｐｈｉｃｓ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔｓ）ｔｏ ａｃｃｅｌｅｒａｔｅ ｔｈｅ ｓｔｅｐ ｏｆ ｄａｔａｂａｓｅ ｓｅａｒｃｈ ａｎｄ ｃａｎｄｉｄａｔｅ ｇｅｎｅｒａｔｉｏｎ．Ａｎｄ ｉｔ ｐｒｅｓｅｎｔｅｄ ａｎ

ｏｐｔｉｍｉｚｅｄ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ＣＵＤＡ（ｃｏｍｐｕｔｅ ｕｎｉｉｆｅｄ ｄｅｖｉｃｅ ａｒｃｈｉｔｅｃｔｕｒｅ）ｐｒｏｇｒａｍｍｉｎｇ ｍｏｄｅｌ ｏｎ ｓｉｎｇｌｅ ＧＰＵ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎ—

ｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ａｖｅｒａｇｅ ｓｐｅｅｄｕｐ ｒａｔｉｏ ｉｓ ｍｏｒｅ ｔｈａｎ ３０，ａｎｄ ｔｈｅ ｍｅｔｈｏｄ ｅｆｆｅｃｔｉｖｅｌｙ ｉｍｐｒｏｖｅｓ ｉｄｅｎｔｉｉｃａｔｉｆｏｎ ｓｐｅｅｄ ａｎｄ ｉｓ

ａｐｐｌｉｃａｂｌｅ ｆｏｒ ｌａｒｇｅ ｓｃａｌｅ ｄａｔａ ｒｅｑｕｉｒｉｎｇ ｆｏｒ ｈｉｇｈ—ｓｐｅｅｄ ｐｒｏｃｅｓｓｉｎｇ．

Ｋｅｙ ｗｏｒｄｓ：ｉｄｅｎｔｉｉｆｃａｔｉｏｎ ｏｆ ｐｏｓｔ—ｔｒａｎｓｌａｔｉｏｎａｌ ｍｏｄｉｉｆｃａｔｉｏｎｓ；ＭＳ—Ａｌｉｇｎｍｅｎｔ；ｇｒａｐｈｉｃｓ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔｓ（ＧＰＵ）；ｃｏｍｐｕｔｅ

ｕｎｉｆｉｅｄ ｄｅｖｉｃｅ ａｒｃｈｉｔｅｃｔｕｒｅ（ＣＵＤＡ）

在生物信息学领域逐渐成为发展趋势，一些研究工作取得了全

０ 引言

研究蛋白质翻译后修饰（ｐｏｓｔ—ｔｒａｎｓｌａｔｉｏｎａｌ ｍｏｄｉｉｆｃａｔｉｏｎｓ）是

新进展，产生了一些基于ＧＰＵ的软件 ’“ 。

由于从基本的图形设备发展到高度并行化的多线程多核

处理器，ＧＰＵ主要用于数据处理而非数据缓存和流控制，非常

适合于计算密集型、高度数据并行化的计算 ” 。本文对

理解各种细胞调节过程的关键，对阐明蛋白质的功能具有重要

作用 。ＭＳ—Ａｌｉｇｎｍｅｎｔ算法是一种非限制性的蛋白质翻译后

修饰鉴定算法，其优点在于卣搜索：在不知道样本中存在哪些

ＭＳ—Ａｌｉｇｎｍｅｎｔ算法进行分析，得出该算法的一个特点是相同的

计算任务在大量数据上重复计算，其为数据并行提供了基础。

ＮＶＩＤＩＡ公司发布的ＣＵＤＡ（ｃｏｍｐｕｔｅ ｕｎｉｉｆｅｄ ｄｅｖｉｃｅ ａｒｃｈｉｔｅｃｔｕｒｅ，

统一计算设备架构）是一种并行编程模型，能促使ＧＰＵ发挥并

行计算的优势，ＣＵＤＡ是Ｃ编程语言的扩展，编程简单，入门容

易 川。本文选择ＣＵＤＡ编程模型设计该算法的关键步骤

翻译后修饰类型的情况下利用串联质谱检索蛋白质序列数据

库，还可以发现一些未知的翻译后修饰 “。。但是ＭＳ—Ａｌｉｇｎ—

ｍｅｎｔ鉴定速度较慢，很难满足快速增长的实验质谱数据和蛋

白质数据库 对提高鉴定速度的要求 。

高性能计算的发展对提升速度做出了巨大贡献。从２００３

即数据库检索及候选肽段生成在ＧＰＵ上的实现方法，并总结

一

年开始，ＧＰＵ（ｇｒａｐｈｉｃｓ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔｓ）就在浮点运算性能和存

储器带宽上将￣ＣＰＵ抛在其后￣７，８ ３，在功耗和成本上也优势明

显 ，而且随着ＧＰＵ上可编程性的增强，ＧＰＵ突破仅用于图形

领域的局限，开始用于一些通用计算 ’ 。ＧＰＵ高性能计算

收稿日期：２０１０．０３．１１；修回日期：２０１０．０４—１２ 基金项目：中国科学院知识创新工程重大项目基金资助项目（ＫＧＧＸ１一Ｙｗ－１３）；ＣＮＩＣ主

些ＧＰＵ优化技巧，最终对其结果进行分析。将ＧＰＵ计算技

术应用于ＭＳ—Ａｌｉｇｎｍｅｎｔ算法的提速是可行的，取得了３０倍以

上的加速比。

ＣＵＤＡ是ＮＶＩＤＩＡ公司发布的用于ＮＶＩＤＩＡ ＧＰＵ上的通用

任基金资助项目（ＣＮＩＣ—ＺＲ ０９００５）；财政部国家重大科研装备研制项目（ＺＤＹＺ２００８－２）；中国科学皖院长奖获得者科研专项基金资助

作者简介：翟艳堂（１９８４．），男，江苏徐州人，硕士，主要研究方向为并行计算（ｚｙｔ０３０３＠１６３．ｃｎ）；涂强（１９８４一），男，工程师，硕士，主要研究方向

为并行计算；郎显宇（１９７９．），女，助研，博士，主要研究方向为生物信息与并行计算；陆忠华（１９６５一），女，研究员，博士，主要研究方向为生物数学与

并行计算；迟学斌（１９６３一），男，研究员，博士，主要研究方向为网格计算、并行计算与软件．

・

３４１０・ 计算机应用研究 第２７卷

并行编程模型，是Ｃ编程语言的扩展 川。使用ＣＵＤＡ编程

时，ＣＰＵ被作为主机（ｈｏｓｔ），ＧＰＵ被作为主机的协处理器（ＣＯ—

ｐｒｏｃｅｓｓｏｒ），被看做执行高度线程化并行处理任务的计算设备

（ｄｅｖｉｃｅ）。运行在ＧＰＵ上的ＣＵＤＡ并行计算函数称为内核

情况（简称Ｍｏｄ＝３＋）。不同的情况计算匹配的方法有所不

同。

本文主要研究的是Ｍｏｄ＝２的情况，对于其他情况亦可借

鉴本文ＧＰＵ加速方法，本文暂不讨论。

输入：一张实验质谱

预处理

Ｔａｇ２￣成

（ｋｅｒｎｅ１），以线程栅格（ ｄ）的形式组织，线程栅格由若干个线

程块（ｂｌｏｃｋ）组成，每个线程块又由若干个线程（ｔｈｒｅａｄ）组成。

使用ｎｖｃｃ编译器编译ＣＵＤＡ源文件，ｋｅｍｅｌ将被编译成设备端

指令。在实际运行中，线程块会被分割为更小的线程束

（ｗａｒｐ），线程束作为真正的执行单位。线程束的大小由硬件的

取数据库中一条蛋白质序列

』

计算该蛋白质序列的任意候选

肽段与实验质谱的匹配分数

输入：一个蛋自质数据库

数据库检索及候选肽段生成 若该分数大于最优匹配分数

还有蛋白质

、、

——

—— —

』

则更新最优匹配

计算能力版本决定，在采用Ｔｅｓｌａ架构的ＧＰＵ中，一个线程束

由连续的３２个线程组成。ＧＰＵ有自己的存储器，称为设备存

储器（ｄｅｖｉｃｅ ｍｅｍｏ￣），相对于ＣＰＵ的主机存储器（ｈｏｓｔ ｍｅｍｏ—

ｒｙ）。ＣＵＤＡ规定了如下的存储器模型：每个线程拥有自己的

一

否

Ｐ埴计算

—

寄存器（ｒｅｇｉｓｔｅｒ）和局部存储器（１ｏｃａｌ ｍｅｍｏ￣）；每个线程块拥

有一块共享存储器（ｓｈａｒｅｄ ｍｅｍｏ￣）；线程栅格中的所有线程

均可以访问全局存储器（ｇｌｏｂａｌ ｍｅｍｏ￣）；所有线程可只读访问

的两种存储器，即常数存储器（ｃｏｎｓｔｌｆＹｌｔ ｍｅｍｏ￣）和纹理存储器

（ｔｅｘｔｕｒｅ ｍｅｍｏ￣）。

上～

否还有实验

输出：最优修饰肽段

一

Ｊ输出最优修饰肽段ｊ

肽段生成主要流程

图１ ＭＳ—Ａｌｉｇｎｍｅｎｔ主要流程

图２数据库检索及候选

Ｍｏｄ＝２的计算匹配方法定义一个ＩＰＩ Ｘ ｆＮｏｄｅｓＩ的矩

１ ＭＳ—Ａｌｉｇｎｍｅｎｔ算法

１．１ 修饰肽段鉴定问题

阵Ｄ７－。其中：Ｐ是蛋白质数据库中某条蛋白质序列，Ｎｏｄｅｓ是

质谱谱峰的集合。

矩阵中每个元素看做是一个节点（ｎｏｄｅ），沿矩阵准对角

线方向构建有向路径，路径上的节点是矩阵的元素（ ， ），边的

起点（ｉ， ）和终点（ ，，）满足ｉ≤ 且 ≤，，某个节点处的分数

符号定义１ Ａ＝｛ａ 一，ａ 。｝代表２０种氨基酸的集合，

ｍａｓｓ（ａ ）代表氨基酸的分子质量。

符号定义２ Ｐ＝ｐ。…Ｐ 代表肽段序列，Ｐ ∈Ａ，其质量为

ｍａｓｓ（Ｐ）＝ ｍａｓｓ（Ｐ ）

代表到达该节点路径的分数。对于矩阵中尚未计算分数的某

点（ｉ， ），以一条最佳（分数最高）的边与已计算分数的某点

（ｉ…，Ｌ ）建立联系而拓展路径，该边的起点和终点分别是

（ｉ…，Ｊｐ ）和（ｉ， ）。

Ｐ在氨基酸Ｐ 处发生修饰变成修饰肽段Ｐ，质量变为ｍａｓｓ

（Ｐ）＋△，△是质量差。

矩阵中某条路径的分数加上某个后缀的分数及位点处的

修饰分数即为某肽段与质谱的匹配分数，当此分数满足一定的

条件时，该路径上的氨基酸和该后缀及位点处的修饰构成的肽

段即为候选肽段。

符号定义３ Ｓ代表实验质谱，其母离子质量ＰＭ等于产

生该质谱的肽段的质量。

符号定义４ ｐｒｅｆｉｘｓｅｏｒｅ（Ｐ ， ）（ｉ≤ ）是肽段前缀Ｐ …Ｐ

打分函数，ｓｕｆｉｆｘｓｃｏｒｅ（ｐ ｐ ）（ｉ ≤ ）是肽段后缀Ｐ ，…ｐ，，打分

函数，ｐｔｍｓｃｏｒｅ（Ａ，Ｐ ）是氨基酸Ｐ 位点处发生修饰△打分函

数，ｓｃｏｒｅ（）代表其他打分函数。

符号定义５ ＤＢ代表蛋白质数据库，其中肽段最多发生

次修饰产生的任意修饰肽段称为候选肽段ｐ，具有最佳匹配分

数的候选肽段称为最优修饰肽段Ｐ 。

修饰肽段鉴定问题（ｍｏｄｉｉｆｅｄ ｐｅｐｔｉｄｅ ｉｄｅｎｔｉｉｆｃａｔｉｏｎ ｐｒｏｂ—

ｌｅｍ）Ｌ２ Ｊ输入：蛋白质数据库ＤＢ，实验质谱Ｓ，修饰发生的次数

候选肽段Ｐ ，…Ｐｊ（ｉ ≤ ＜ ）与质谱的匹配分数为

Ｄ：Ｄ Ｐ ， ）＋ｓｕｆｉｆｘｓｃｏｒｅ（ｐ ＋１，ｐ ） ｐｔｍｓｅｏｍ（Ａ，Ｐ ＋１） （１）

其中：Ｐ ∈Ｐ，ｎ ∈Ｎｏｄｅｓ；ｍｉｎ￣≤△≤ｍａ】（△，ｒｎｉｎ￣、ｍａｘＡ分别为修

饰质量差的最小值和最大值。

矩阵中某点的分数：

ＤＴ（ｐ ，ｎ ）＝ｓｃｏｒｅ（ｍａｓｓ（ｎ＾））＋ｂｅｓｔｓｃｏｒｅ （２）

其中：

ｂｅｓｔｓｃｏｒｅ＝ｍａｘ｛

初始值：ｓｔａｒｔｓｃｏｒｅ（ｐ ）；

；输出：最优修饰肽段 。

１．２ ＭＳ—Ａｌｉｇｎｍｅｎｔ（Ｍｏｄ＝２）算法描述

ＭＳ—Ａｌｉｇｎｍｅｎｔ算法主要由预处理（ｐｒｅｐｒｏｃｅｓｓｉｎｇ）、Ｔａｇ生成

（Ｔａｇ ｇｅｎｅｒａｔｉｏｎ）、数据库检索及候选肽段生成（ｄａｔａｂａｓｅ ｓｅａｒｃｈ

＆ｃａｎｄｉｄａｔｅ ｇｅｎｅｒａｔｉｏｎ）和Ｐ值计算（Ｐ—ｖａｌｕｅ ｃｏｍｐｕｔａｔｉｏｎ）几个

／ｎａｘ｛Ｄ Ｐ ，ｅｄｇｅ．ｔｏｎｏｄｅ）＋ｓｃｏｒｅ（ｅｄｇｅ）Ｉ ｅｄｇｅ∈｛ｎ 向后跨度

ｍａｓｓ（ ）的边｝｝；

ｍａｘ｛ＤＴ（ｐＨ，ｅｄｇｅｄｏｕｂｌｅ．ｔｏｎｏｄｅ）＋ｓｃｏｒｅ（１／２ｍａｓｓ（ｅｄｇｅｄ０ｕｂｌｅ））＋

ｓｃｏｒｅ（ｅｄｇｅｄｏｕｂｌｅ）Ｉ ｅｄｇｅｄｏｕｂｌｅ∈｛ 向后跨度ｍａｓｓ（ｐＨＰｒ）的边｝ｌ；

ｍａｘ｛Ｄｒ（ｐ 一３，ｅｄｇｅｔｒｉｐｌｅ．ｔｏｎｏｄｅ）＋ｓｃｏｒｅ（Ｉ／３ｍａｓｓ（ｅｄｇｅｔｒｉｐｌｅ））＋

步骤组成，如图１所示。数据库检索及候选肽段生成是其关键

步骤，如图２。计算蛋白质序列的任意候选肽段与实验质谱的

匹配分数（简称计算匹配，下同）是数据库检索部分的重要部

分 。Ｍｓ－Ａｌｉｇｎｍｅｎｔ依据限定修饰发生的次数分成三个模

块，即最多有一个翻译后修饰情况（简称Ｍｏｄ＝１）、最多有两

ｓｃｏｒｅ（２／３ｍａｓｓ（ｅｄｇｅｔｒｉｐｌｅ））＋ＳＣＯＩＤ（ｅｄｇｅｔｒｉｐｌｅ）ｌ ｅｄｇｅｔｒｉｐｌｅ∈｛ 向后跨

度ｍａｓｓ（ｐ ２Ｐ Ｐ ）的边｝｝；

ｍａｘ｛Ｄ Ｐ ，，ｎ０）＋ｐｒｅｆｉｘｓｃｏｒｅ（ｐ Ｐ ）１０＜ｉ ≤ｉ｝；

ｍａｘ｛ＤＴ（ｐ ，，Ｈｏ）＋ｐｒｅｆｉｘｓｃｏｒｅ（ｐ 一，Ｐ ）＋ｐｔｍｓｅｏｒｅ（Ａ，Ｐ ）１０＜ｉ ≤ｉ，

ｍｉｎＡ≤△≤ｍａ）【△｝：

｝

１．３ ＭＳ—Ａｌｉｇｎｍｅｎｔ（Ｍｏｄ＝２）算法性能分析

对ＭＳ—Ａｌｉｇｎｍｅｎｔ（Ｍｏｄ＝２）算法进行分析得出其计算时间

个翻译后修饰情况（简称Ｍｏｄ＝２）和最多有多个翻译后修饰 复杂度为０（ ・ ・ｍ ・ｍ ・Ｍｊ）。其中： 为实验质谱的

第９期 翟艳堂，等：基于ＣＵＤＡ的蛋白质翻译后修饰鉴定ＭＳ—Ａｌｉｇｎｍｅｎｔ算法加速研究 ・３４１１・

２．１．２使用ＧＰＵ加速的可行性

数量， 为蛋白质数据库中蛋白质序列条数，ｍ 是蛋白质序

列长度，即构成该蛋白质的氨基酸个数，ｍ 是质谱谱峰数，

是修饰质量差跨度。然后进行实际数据测试，测试使用的实验

质谱由中国科学院上海生命科学研究院盛泉虎博士提供；蛋白 个特点是相同的计算任务在不同的数据上重复计算，此特点

质数据库采用ｉｐｉ．ＭＯＵＳＥ．ｖ３．２９．ＲＥＶＥＲＳＥＤ（１０７ ９６２条蛋白

质序列）由盛泉虎博士提供，ｕｎｉｐｒｏｔ—ｓｐｒｏｔ（４６６ ７３９条蛋白质序 质序列划分成一个个小肽段，是一种细粒度的数据划分。

列）来源于ＥＭＢＬ—ＥＢＩ（Ｅｕｒｏｐｅａｎ Ｍｏｌｅｃｕｌａｒ Ｂｉｏｌｏｇｙ Ｌａｂｏｒａｔｏｒｙ— ＭＳ—Ａｌｉｇｎｍｅｎｔ（Ｍｏｄ＝２）移植到ＧＰＵ上之后，ＧＰＵ上不同

Ｅｕｒｏｐｅａｎ Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ Ｉｎｓｔｉｔｕｔｅ，欧洲分子生物学实验室暨欧洲

生物信息学中心）。

对ＭＳ—Ａｌｉｇｎｍｅｎｔ（Ｍｏｄ＝２）算法分析可得其计算任务在不

同的实验质谱、不同的蛋白质序列上重复计算，因此该算法的

一

为数据并行提供了基础。对蛋白质数据库进行划分，是将蛋白

的线程采用相同的任务处理不同的数据，之间数据相关性比较

小而且不复杂，可以采取ＣＵＤＡ提供的通信机制 和编程者

采取其他方法有效解决。

２．２ ＤＣＧＰＵＭ ２算法描述

在表１所列的环境１下，统计了该算法在输入不同质谱数

量和不同规模蛋白质数据库的情况下的计算时间，如图３所

示；采用文献［６］的程序统计了在环境３集群上的计算时间如

图４所示。

表ｌ硬件环境

环境 硬件配置

ｌ ＣＰＵ：ＡＭＤ Ｐｈｅｎｏｍ ９８５０ ２．５ ＧＨｚ；Ｍｅｍｏｒｙ：８ ＧＢ

ＣＰＵ：Ｉｎｔｅｌ Ｘｅ。“Ｅ５４１０ ２・３３ ＧＨ ；Ｍ ｍ。ｒｙ：８ ＧＢ；

ＧＰＵ：ＮＶＩＤＩＡ Ｔｅｓｌａ Ｃ１０６０ １．４４ ＧＨｚ：Ｃｏｍｐｉｌｅｒ：ｎｖｃｃ ２ ２

Ｃｌｕｓｔｅｒ：１８个计算节点，每个节点配置一颗ｌｎｔｅｌ Ｘｅｏｎ

３

Ｅ５４１０四核处理器，２ ３３ ＧＨｚ，８ ＧＢ内存

３

２

１

１

‘＝１

ｓｐｅｃｔｒａ ｓｅａｒｃｈｅｄ ｓｐｅｃｔｒａ ｓｅａｒｃｈｅｄ

图３ ＭＳ—Ａｌｉｇｎｍｅｎｔ（Ｍｏｄ：２） 图４ Ｍｓ—Ａ１ｉｇｎｍｅｎｔ（Ｍ０ｄ＝２）

ＣＰＵ串行执行时间 在ｃｌｕｓｔｅｒ上的执行时间

进一步对算法各步骤计算时间占整个计算时间的比重进

行统计分析，得到步骤数据库检索及候选肽段生成的计算时间

占９９．９％以上。因此，如果能降低此部分的计算时问，则整个

流程的计算时间就能有效地减少。

２ ＧＰＵ加速算法ＤＣＧＰＵＭ ２

２．１ ＭＳ—Ａｌｉｇｎｍｅｎｔ（Ｍｏｄ＝２）使用ＧＰＵ加速的原因和可行性

２．１．１ 使用ＧＰＵ加速的原因

ＧＰＵ的设计能使更多晶体管用于数据处理而非数据缓存

和流控制，特别适合于计算密集型、高度数据并行化的计

算 。众多的处理核心（如ＮＶＩＤＩＡ Ｔｅｓｌａ Ｃ１０６０有２４０个处

理核心）使数据细粒度并行化更高。

ＭＳ．Ａｌｉｇｎｍｅｎｔ需要两种数据，即实验质谱和蛋白质数据

库。而且数据量较大、计算时间长。根据图３的增长趋势，当

实验质谱有５０ ０００张、蛋白质数据库采用ｉｐｉ．ＭＯＵＳＥ．ｖ３．２９．

ＲＥＶＥＲＳＥＤ时 鉴定时间可达２６ ７１５ ｈ（３年左右）；蛋白质数

据库采用ｕｎｉｐｒｏｔ—ｓｐｒｏｔ时，鉴定时间可达９４ ４３２ ｈ（１０年左

右），在集群上也可达２ ７７０ ｈ（３．８５个月左右）。当质谱数量

和数据库规模较大时，算法不能很好地满足鉴定速度的要求，

需要采用高性能计算加速鉴定过程。可对上述两种数据进行

划分，即实验质谱是粗粒度数据并行；蛋白质数据库是细粒度

数据并行。在划分质谱的基础上进一步对蛋白质数据库进行

划分可带来更高的加速效果，而对蛋白质数据库的细粒度数据

并行适合采用ＧＰＵ处理。

借鉴加利福尼亚大学圣地亚哥分校计算质谱中心（Ｃｅｎｔｅｒ

ｆｏｒ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｍａｓｓ Ｓｐｅｃｔｒｏｍｅｔｒｙ，Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｃａｌｉｆｏｒｎｉａ，Ｓａｎ

Ｄｉｅｇｏ）实现ＭＳ—Ａｌｉｇｎｍｅｎｔ算法的代码，设计数据库检索及候选

肽段生成在单ＧＰＵ上实现的算法ＤＣＧＰＵＭ２（ｄａｔａｂａｓｅ ｓｅａｒｃｈ

ａｎｄ ｃａｎｄｉｄａｔｅ ｇｅｎｅｒａｔｉｏｎ ｕｓｉｎｇ ＧＰＵ ｆｏｒ Ｍｏｄ＝２）。数据划分的

方法如下：将数据库中所有的蛋白质序列看成一整条序列；将

该序列划分成等长的序列段依次用ＧＰＵ处理；在ＧＰＵ内，将

序列段划分到多个线程块上；在线程块内，将序列段划分成更

小的序列段分配到多个线程，线程之间共享一部分小序列片

段，具体如图５所示。ＤＣＧＰＵＭ２主要流程如图６所示。将蛋

＼、¨

白质数据库中的所有序列看成一条序列ＰＷ。

…………＿●

ＧＰＵ ＧＰＵ ＧＰＵ ＧＰＵ

翟

，

，

、

。

＿・

ｔｈｒｅａｄ ｔｈｔ：ｅａｄ

图５ ＤＣＧＰＵＭ２数据划分方式 图６ ＤＣＧＰＵＭ２主要流程

第一个内核：ｋｅｒｎｅｌｌ。每个线程计算以序列ＰＷ的氨基

酸Ｐ 开始长度为３２的肽段Ｐ＝Ｐ …Ｐ 中每个前缀ＰⅢ 的质

量和分数，并且Ｐ。 也是以Ｐ 作为开始氨基酸。其结果存储

在全局存储器空间。

第二个内核：ｋｅｍｅ￣。每个线程计算以序列ＰＷ的氨基酸

ｐ ，结束长度为３２的肽段Ｐ：ｐ …Ｐ ，中每个后缀Ｐ 的质量

和分数，并且Ｐ 也是以Ｐ 作为结束氨基酸。其结果存储在

全局存储器空间。

第三个内核：ｋｅｒｎｅｌ３。采用式（２）动态规划地填充表Ｄ

每个线程填充一列，在计算表中每个元素值时，考虑前缀处发

生一次修饰，而且与ＤＴ左上角的某些值具有数据相关性，如

图７所示。因为不同线程之间具有数据相关性，在填充一个元

素之后需要全局同步，如图８所示。

第四个内核：ｋｅｒｎｅｌ４。遍历ＤＴ表，查找候选肽段。每个

线程遍历一列，遍历到表中每个元素时，考虑后缀处发生一次

修饰。

２．３算法实现优似

存储器带宽是计算机性能的瓶颈之一，在以运算为主的

ＣＵＤＡ程序中，应尽量避免让存储器访问和通信成为性能瓶

颈；而在以存储器访问为主的应用中，应尽可能增大程序的可

・

３４１２・ 计算机应用研究 第２７卷

用带宽 。每种存储器的高效带宽较大程度地依赖于存储器

（ｃｏａｌｅｓｃｅｄ ａｃｃｅｓｓ），而且使用共享存储器不出现存储体冲突，

不出现使用共享存储器过多而造成线程块并发性降低或ｋｅｒ－

的访问模式 ”， ］，实现存储器的最大可用带宽是ＣＵＤＡ程序

优化的重要任务之一 。 ｎｅ】启动失败 等等。如果不出现存储体冲突，访问共享存储

图７填充Ｄ ７－表数据相关性 图８全局同步

１）全局同步（ｇｌｏｂａｌ ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ）

２．２节中提到采用动态规划的方式填充表ＤＴ，在计算表

中每个元素值时，与ＤＴ左上角的某些值具有数据相关性。这

样不同的线程之间具有数据相关性，而且跨线程块的线程之间

具有数据相关性，因此在填充一个元素之后需要全局同步。

ＣＵＤＡ提供的ｋｅｒｎｅｌ函数内同步指令有：ｓｙｎｃｔｈｒｅａｄｓ（）、

ｔｈｒｅａｄｆｅｎｅｅ

—

ｂｌｏｃｋ（）、一ｔｈｒｅａｄｆｅｎｃｅ（），前两者是线程块内同步，

后者可用于全局同步” ；启动ｋｅｒｎｅｌ也可以作为全局同步

点 』。两种方法均可以用于本文：ｋｅｒｎｅｌ函数内循环运算，采

用一ｔｈｒｅａｄｆｅｎｃｅ（）函数全局同步；ｋｅｒｎｅｌ函数外循环运算，采用

启动ｋｅｒｎｅｌ作为全局同步点。经比较，后者比前者性能提升

８．４６％左右（图９）。

２）使用分页锁定存储器（ｐａｇｅ—ｌｏｃｋｅｄ ｍｅｍｏ￣）

ＮＶＩＤＩＡ Ｔｅｓｌａ Ｃ１０６０通过ＰＣＩ Ｅ总线与主机端连接，一条

ＰＣＩ．Ｅ ２．０ １６ｘ总线的理论带宽是双向每向８ ＧＢｐｓ，远小于显

存和ＧＰＵ片上存储器带宽。ＰＣＩ—Ｅ总线带宽很容易成为整个

程序性能提升的瓶颈。使用分页锁定存储器的优势之一是主

机端与设备端之间的存储带宽较高 。使用分页锁定存储器

产生３２．３７％左右的性能提升（图９），性能提升在于主机端和

设备端数据传输部分。 不使用分页锁定存储器时，主机端向设

备端数据传输带宽为１．６３ ＧＢｐｓ，设备端向主机端数据传输带

宽为１．９４ ＧＢｐｓ；使用分页锁定存储器后，两者分别增至２．４７

ＧＢｐｓ和５．１１ ＧＢｐｓ。

３）使用纹理存储器（ｔｅｘｔｕｒｅ ｍｅｍｏ￣）

纹理存储器有缓存且对二维空间局域性缓存有优化，因此

访存性能较高 』，而且其空问比常数存储器空间大得多：在通用

计算中非常适合用于图像处理或查找表，对大量数据的随机访

问或非对齐访问也有良好的加速效果… 。本文ｋｅｒｎｅｌ函数中

要随机地查找一些表，而且只读，适合采用纹理存储器存储这些

表。质谱节点向后跨度一个氨基酸的表，在ｈｏｓｔ端代码中用链

表存储结构，使用指针数据类型，而在ｄｅｖｉｃｅ端代码ｋｅｒｎｅｌ函数

中不能再使用这种结构，而且在ｋｅｒｎｅｌ函数中对其只读。观察

此表，其具有稀疏矩阵的形态，采用行压缩格式存储在纹理存储

器空间，一些具有同样特点的表也采用这种方式存储。采用行

压缩存储格式能节省存储空间，采用纹理存储器是缘其优点。

使用纹理存储器带来约３Ｏ．９４％的性能提升（图９）。

４）使用共享存储器（ｓｈａｒｅｄ ｍｅｍｏｒｙ）及避免存储体冲突

（ｂａｎｋ ｃｏｎｆｌｉｃｔ）

使用共享存储器或充分使用共享存储器不是提高性能的

充要条件，但是如果ｋｅｒｎｅｌ函数的特点适合采用共享存储器则

可用之。例如，线程块内线程共享数据或通信，线程需要对全

局存储器空间多次访问或全局存储器访问不能构成联合访问

器几乎和访问寄存器一样快。本文的ｋｅｎｒｅｌ函数中不同的线

程共享一部分数据，而且这些数据存储在全局存储器中，因此

本文采用共享存储器在不同的线程之间共享数据而减少重复

频繁地访问全局存储器。共享存储器的元素类型占４ Ｂｙｔｅ，访

存索引与线程号对应，避免存储体冲突。使用共享存储器产生

４．９％左右的性能提升，如图９所示。

ｓｐｅｃｔｒｕｍ：ｈｉｓｔｏｎｅＦＴ

１．１０００３ １０００３．２ Ｊ １日增加时间

１２Ｏ

ｄａｔａｈ ＿ｌｌｎｉｎｒｏｔ ｓｎｒｎｔ Ｉ１矗优化后时间

１０Ｏ

８Ｏ

＿ｌ ］１ｉ

４．９％

６０

４０

７

７４．８７

２０

０

优化后ｋ… ｌ内循环 未使用分页 未使用 未使用

锁定存储器纹理存储器共享存储器

图９ ＧＰＵ优化性能提升

５）全局存储器联合访问（ｃｏａｌｅｓｃｅｄ ａｃｃｅｓｓ）

全局存储器访问延时是４００～６００时钟周期（ｃｌｏｃｋ ｃｙｃｌｅ），

而且不会被缓存，经常成为性能提升的障碍，因此采用正确的

访问模式来实现最大化的存储器带宽尤为重要。全局存储器

联合访问，即半ｗａｒｐ块中的线程进行的全局存储器访问可结

合成一个存储器事务时，全局存储器带宽的使用效率将达到最

高 。本文具体采用以下方式：

ａ）将氨基酸以字符（ｃｈａｒ）的形式存储，在全局存储器中占

８ ｂｉｔ；蛋白质的氨基酸序列顺序存储，不同的线程顺序访问序

列中的氨基酸，这样可构成全局存储器的联合访问。

ｂ）使用内嵌的数据类型ｉｎｔ２存储质量和分数，使用ｕｉｎｔ２

类型存储地址值，使不同的线程按顺序访问全局存储器。

ｃ）如果将申请的全局存储器空间看成逻辑二维表，则每

个线程按列访问，不同线程按行顺序访问 ，如图ｌ０所示。

３性能分析

采用１．３节中同样的实验质谱和蛋白质数据库；ＧＰＵ计

算环境为表１中的环境２，与其对比的是环境ｌ和３；环境３上

的并行程序采用文献［６］中的程序。

３．１加速比分析

统计了ＧＰＵ加速后整个流程的计算时间，如图１１所示。

根据图１１的增长趋势，当实验质谱有５０ ０００张、蛋白质数据

库采用ｉｐｉ．ＭＯＵＳＥ．ｖ３．２９．ＲＥＶＥＲＳＥＤ时，鉴定时间约需７５０ ｈ

（３１天左右），蛋白质数据库采用ｕｎｉｐｒｏｔ—ｓｐｒｏｔ时，鉴定时间约

需２ ５２５ ｈ（３．５１个月左右）。

由 甲 甲甲

…

一＿一一一一一一一一一

芷

＾［［圈…．．口图

；；；； ；；；； 喜

第９期 翟艳堂，等：基于ＣＵＤＡ的蛋白质翻译后修饰鉴定ＭＳ—Ａｌｉｇｎｍｅｎｔ算法加速研究 ・３４１３・

ＧＰＵ相对于集群１８个节点（７２颗处理器）的加速比分别如图 次传输的数据量。本文申请的全局存储器空间量约为７７

１２～１５。由图可见，输入不同质谱数量和不同蛋白质数据库规

模的情况下，单ＧＰＵ相对于单ＣＰＵ的加速比略有不同，核心 储器空间，循环处理ＤＣＧＰＵＭ２流程，每次使用不同块空问，最

函数的加速比略高于整个流程的加速比，但性能提升均在３０

倍以上，而且当数据库规模较大时，加速比在４１倍以上。

：：！： ！： ！ 翌 ！１２：！！＝！ ：！１

ｇ－４ｏ

＿８；ｓ髫 ３９． ， ９ｌ＿

３０

晏２ｏ

１０

０

ｓｐｅｃｔｒａ ｓｅａｒｃｈｅｄ

图１２数据库检索及候选肽段生成单ＧＰＵ相对于

单ＣＰＵ的加速比

呈

墓５０

ｗ

ｈ

ｏｌｅｆｌｏＳＥ．ｖ３２９．ＲＥＶＥＲＳＥＤ

ｗ

ＨＫｑｉｐｉ

ＭＯＵ

Ｄｕｎ

ｉ

ｐｒ￣ｔ－ｐｒ￣

ｓ

．．

４ｌ ３５ ４ｌ ９１ ４２．１

…

，１ ５５ ４ｌ ３７

｝４０

３０

姜２０

１０

０ Ｉ ＿Ｌ＿． ．ｉ． ＿＝ｉ。 ．０． Ｉ

１ ５ １０ ５０ １００

ｓｐｅｃｔｒａ ｓｅａｒｃｈｅｄ

图１ ３整个流程单ＧＰＵ相对于单ＣＰＵ的加速比

７ｌ ｌ４２ ２】３ ２８４ ３５５ ４２６ ４９７

ｓｐｅｃｔｒａ ｓｅａｒｃｈｅｄ

图１４整个流程单ＧＰＵ计算 图１５整个流程单ＧＰＵ相对于

时间与集群计算时间的比较 集群的加速比

ＤＣＧＰＵＭ２是对蛋白质数据库而不是质谱数据进行划分，

虽然不同质谱计算时问不一定相同，但当质谱数量较大时，整

个流程单ＧＰＵ计算时间与质谱数量大致呈正比关系，因此在

图１１和１４中，整个流程单ＧＰＵ计算时问增长方式大致呈线

性。由１．３节可知，整个流程单ＣＰＵ计算时间与质谱数量也

大致呈正比关系；数据库检索及候选肽段生成步骤的计算时间

与质谱数量也呈正比关系。因此，整个流程单ＧＰＵ相对于单

ＣＰＵ的加速比和数据库检索及候选肽段生成单ＧＰＵ相对于单

ＣＰＵ的加速比基本稳定，与质谱数量没有关系。

在图４和ｌ４中，整个流程在集群上的计算时间随质谱数

量的增加而增加，但不是正比关系。输入质谱数量不同的情况

下，负载平衡效率不同，最优情况是负载平衡效率为１００％，但

往往负载平衡效率不高。。Ｊ。之所以在图１５中，质谱数量为

４２６处所对应的加速比仅为０．９７，比图中其他值都小，是因为

质谱数量为４２６时，集群处理器负载平衡效率比其他处高，造

成集群计算时间与质谱数量的比率较低。

本文在算法实现上采用多种优化方法，得到了较高的加速

比，但笔者认为尚有进一步性能提升的空间，可以在以下方面

作进一步优化：

ａ）主机与设备之间的数据传输。主机与设备之间的数据

传输时间占ＤＣＧＰＵＭ２执行时间的３ｌ％以上，如图１６所示，减

少此部分时间对性能提升是有效的。可采用下面两种优化

途径：

（ａ）采用流操作，以期达到数据传输与内核执行之间异

步，减少程序执行时间。

（ｂ）整块数据传输而不是多次分小块传输 ，并且增大

一

ＭＢ，远小于Ｔｅｓｌａ Ｃ１０６０显存量。可以一次申请较大的全局存

后将整块数据一次传输。

ｂ）控制流指令。控制流指令一般会影响有效指令吞吐

量，降低ＧＰＵ程序执行性能 ，但是文献［１７］中提出：如果只

需要少量线程进行操作，使用类似“ｉｆ ｔｈｒｅａｄｌｄｘ＜Ｎ”的方式避

免多个线程同时运行占用更长时问。可采用下面两种优化

途径：

（ａ）修改控制条件，尽量避免在ｗａｒｐ内发生分支，如使控

制条件依赖于ｔｈｒｅａｄｌｄｘ／ｗａｒｐＳｉｚｅ（其中ｔｈｒｅａｄｌｄｘ为线程ＩＤ，

ｗａｒｐＳｉｚｅ为ｗａｒｐ大小） 。

（ｂ）循环展开，使用＃ｐｒａｇｍａ ｕｎｒｏｌｌ指令，或者编写程序时

不使用循环语句而直接将循环展开。

ｅ）ＧＰＵ加速算法。如果能在ＧＰＵ并行算法上进一步优

化，则性能提升空间将更大。

４０

ｇ ３０

量２０

奎１０

０

４结束语

本文在深入分析ＭＳ—Ａｌｉｇｎｍｅｎｔ（Ｍｏｄ＝２）算法的基础上，

总结该算法的特点，提出了该算法核心计算模块数据库检索及

候选肽段生成的单ＧＰＵ加速实现方法，总结了一些优化技巧，

针对不同情况采取相应的优化措施。测试结果表明，基于

ＧＰＵ的算法比ＣＰＵ上的串行算法提速明显，相对于集群也有

加速，可以满足大规模数据对鉴定速度的要求，ＧＰＵ高性能计

算在蛋白质翻译后修饰鉴定中的应用对计算蛋白质组学海量

数据处理提供了一种新的思路。ＧＰＵ用于并行计算及ＣＵＤＡ

编程具有优势，但也具有一些缺点。本文利用ＧＰＵ并行计算

的思想和优化的技巧可以被借鉴于蛋白质翻译后修饰鉴定其

他算法的加速优化和ＧＰＵ集群机器上的加速优化。ＭＳ—

Ａｌｉｇｎｍｅｎｔ算法是用实验质谱查询蛋白质数据库，鉴于此，可以

・

３４１４・ 计算机应用研究 第２７卷

将ＧＰＵ加速ＭＳ—Ａｌｉｇｎｍｅｎｔ的思想推广到基于质谱技术的计算

蛋白质组学的其他研究方面，如蛋白质鉴定（ｐｒｏｔｅｉｎ ｉｄｅｎｔｉｉｆｃａ—

ｔｉｏｎ）、氨基酸序列分析（ａｍｉｎｏ ａｃｉｄ ｓｅｑｕｅｎｃｅ ａｎａｌｙｓｉｓ）等，还可

［１１］ＮＶＩＤＩＡ Ｃｏｒｐｏｒａｔｉｏｎ．Ｔｅｓｌａ ＢＩＯ Ｗｏｒｋｂｅｎｃｈ一助力新型科学［ＥＢ／

ＯＬ］．［２０１０ ０３－１１］．ｈｔｔｐ：／／ｗｗｗ．ｎｖｉｄｉａ．ｅｎ／ｏｂｊｅｅｔ／ｔｅｓｌａ＿ｂｉｏ＿ｗｏｒｋ—

ｍ１． ｃｎ．ｈｔ

ｂｅｎｃｈ

—

以推广到其他领域，如蛋白质序列比对（ｐｒｏｔｅｉｎ ｓｅｑｕｅｎｃｅ ａｌｉｇｎ—

ｍｅｎｔ）、基因序列比对（ｇｅｎｅ ｓｅｑｕｅｎｃｅ ａｌｉｇｎｍｅｎｔ）等。

参考文献：

［１］ＮＡ Ｓ Ｊ，ＪＥＯＮＧ Ｊ Ｈ，ＰＡＲＫ Ｈ Ｊ，ｅｔ ａ１．Ｕｎｒｅｓｔｒｉｃｔｉｖｅ ｉｄｅｎｔｉｉｆｃａｔｉｏｎ ｏｆ

ｍｕｌｔｉｐｌｅ ｐｏｓｔ．．ｔｒａｎｓｌａｔｉｏｎａｌ ｍｏｄｉｉｆｃａｔｉｏｎｓ ｆｒｏｍ ｔａｎｄｅｍ ｍａｓｓ ｓｐｅｅｔｒｏｍｅ—

ｔｒｙ ｕｓｉｎｇ ａｎ ｅｒｒｏｒ—ｔｏｌｅｒａｎｔ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｆｉｎ ｅｘｔｅｎｄｅｄ ｓｅｑｕｅｎｃｅ

［１２］ＮＶＩＤ１Ａ Ｃｏｒｐｏｒａｔｉｏｎ．Ｔｅｓｌａ Ｂｉｏ Ｗｏｒｋｂｅｎｃｈ帮助科学家在生物科学

领域取得全新突破［ＥＢ／ＯＬ］．［２０１０—０３－１ １］．ｈｔｔｐ：／／ｗｗｗ．ｎｖｉｄｉａ．

ｃｎ／ｏｂｊｅｃｔ／ｉｏ—．１２６４４０５２４８４１６．ｈｔｍ１．

［１３］ＳＣＨＡＴＺ Ｍ Ｃ，ＴＲＡＰＮＥＬＬ Ｃ，ＤＥＬＣＨＥＲ Ａ Ｌ，ｅｔ ａ１．Ｈｉｇｈ－ｔｈｍｕ￣－

ｐｕｔ ｓｅｑｕｅｎｃｅ ａｌｉｎｍｅｎｔｇ ｕｓｉｎｇ ｇｒａｐｈｉｃｓ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔｓ［Ｊ］．ＢＭＣ

Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ，２００７，８（１）：４７４．

［１４］ＩＪＵ Ｙｏｎｇ—ｃｈａｏ，ＭＡＳＫＥＬＬ Ｄ Ｌ，ＳＣＨＭＩＤＴ Ｂ．ＣＵＤＡＳＷ＋＋：０ｐ－

ｔｉｍｉｚｉｎｇ Ｓｍｉｔｈ－Ｗａｔｅｒｍａｎ ｓｅｑｕｅｎｃｅ ｄａｔａｂａｓｅ ｓｅａｒｃｈｅｄ ｆｏｒ ＣＵＤＡ—ｅｎａ－．

ｔａｇ ａｐｐｒｏａｃｈ［Ｊ］．Ｍｏｌｅｃｕｌａｒ ａｎｄ Ｃｅｌｌｕｌａｒ Ｐｒｏｔｅｏｍｉｃｓ，２００８，７

（１２）：２４５２—２４６３．

ｂｌｅｄ ｇｒａｐｈｉｃｓ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔｓ［Ｊ］．ＢＭＣ Ｒｅｓｅａｒｃｈ Ｎｏｔｅｓ，２００９，２

（Ｊ）：７３．

［２］ＴＳＵＲ Ｄ，ＴＡＮＮＥＲ Ｓ。ＺＡＮＤＩ Ｅ，ｅｔ ａ１．Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ｏｆ ｐｏｓｔ—ｔｒａｎｓｌａ—

ｔｉｏｎａｌ ｍｏｄｉｉｆｃａｔｉｏｎｓ ｖｉａ ｂｌｉｎｄ ｓｅａｒｃｈ ｏｆ ｍａｓｓ ｓｐｅｃｔｒａ［Ｊ］．Ｎａｔｕｒｅ Ｂｉｏ—

ｔｅｃｈｎｏｌｏｇｙ，２００５，２３：１５６２－１５６７．

［１ ５］ＬＩＧＯＷＳＫＩ Ｌ，ＲＵＤＮＩＣＫＩ Ｗ．Ａｎ ｅｆｉｆｃｉｅｎｔ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｓｍｉｔｈ

ｗａｔｅｒｍａｎ ａｌｇｏｒｉｔｈｍ ｏｎ ＧＰＵ ｕｓｉｎｇ ＣＵＤＡ．ｆ０ｒ ｍａｓｓｉｖｅｌｙ ｐａｒｌｌｅｌａ ｓｃａｎ—

［３］谢靖宇，谢深泉．一种鉴定蛋白质突变和翻译后修饰的算法

［Ｊ］．计算机工程与应用，２００７，４３（２８）：６１．６４．

［４］ＦＲＡＮＫ Ａ Ｍ．Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｔａｎｄｅｍ ｍａｓｓ ｓｐｅｃｔｒｏｍｅｔｒｙ—ｂａｓｅｄ ｐｒｏ．

ｔｅｏｍｉｅｓ［Ｄ］．Ｓａｎ Ｄｉｅｇｏ：Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｃａｌｉｆｏｒｎｉａ，２００８．

［５］ＭＡＮＡＶＳＫＩ Ｓ Ａ，ＶＡＬＬＥ Ｇ．ＣＵＤＡ ｃｏｍｐａｔｉｂｌｅ ＧＰＵ ｃａｒｄｓ ａｓ ｅｆｉｆ．

ｃｉｅｎｔ ｈａｒｄｗａｒｅ ａｃｃｅｌｅｒａｔｏｒｓ ｆｏｒ Ｓｍｉｔｈ－Ｗａｔｅｒｍａｎ ｓｅｑｕｅｎｃｅ ａｌｉｇｎｍｅｎｔ

ｎｉｎｇ ｏｆ ｓｅｑｕｅｎｃｅ ｄａｔａｂａｓｅｓ［Ｃ］／／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ ｗ０ｒｋ—

ｓｈｏｐ Ｏｌｌ Ｈｉｇｈ Ｐｅｒｆｏｒｍａｎｃｅ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｂｉｏｌｏｇｙ．２００９：ｌ一８．

［１６］ＫＩＲＫ Ｄ，ＨＷＵＷｅｎ－ｍｅｉ．ＥＣＥ ４９８ＡＬ：ａｐｐｌｉｅｄ ｐａｒｌｌａｅｌ ｐｒｏｇｒａｍｍｉｎｇ

［ＥＢ／ＯＬ］．（２０１０）［２０１０—０３－１ １］．ｈｔｔｐ：／／ｃｏｕｒｓｅｓ．ｅｃｅ．ｉｌｌｉｎｏｉｓ．

ｅｄｕ／ｅｃｅ４９８／ａＬ／．

［１７］张舒，褚艳利．ＧＰＵ高性能运算之ＣＵＤＡ［Ｍ］．北京：中国水利

水电出版社，２００９：１４，４４，５８，１４３，１５２，１６６．

［Ｊ］．ＢＭＣ Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ，２００８，９（Ｓｕｐｐｌ ２）：Ｓ１０．

［６］涂强．蛋白质翻译后修饰鉴定软件ＩｎｓＰｅｃＴ的并行及优化研究

［Ｄ］．北京：中国科学院研究生院，２００９．

［７］ＮＶＩＤＩＡ Ｃｏｒｐｏｒａｔｉｏｎ．ＮＶＩＤＩＡ ＣＵＤＡ Ｐｒｏｇｒａｍｍｉｎｇ Ｇｕｉｄｅ ｖｅｒｓｉｏｎ ２．

３．１［Ｒ］．２００９．

［８］ＦＥＳＴＥＲ Ｔ，ＳＣＨＲＥＩＢＥＲ Ｆ，ＳＴＲＩＣＫＥＲＴ Ｍ．ＣＵＤＡ ｂａｓｅｄ ｍｕｌｔｉ—

ｃｏｌｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ＭＤＳ—ｂａｓｅｄ ｂｉｏｉｎｆｏｒｍａｔｉｃｓ ａｌｇｏｒｉｔｈｍｓ［Ｃ］／／

．

［１８］ＴＡＮＮＥＲ Ｓ，ＳＨＵ Ｈｏｎｇ－ｊｕｎ，ＦＲＡＮＫ Ａ，ｅｔ ａ１．Ｉｎｓｐｅｃｔ：ｆａｓｔ ａｎｄ ａｃ—

ｃｕｒａｔｅ ｉｄｅｎｔｉｉｆｃａｔｉｏｎ ｏｆ ｐｏｓｔ－ｔｒａｎｓｌａｔｉｏｎａｌｌｙ ｍｏｄｉｉｆｅｄ ｐｅｐｔｉｄｅｓ ｆｒｏｍ ｔａｎ－

ｄｅｍ ｍａｓｓ ｓｐｅｃｔｒａ［Ｊ］．Ａｎａｉｌｙｔｉｃａｌ Ｃｈｅｍｉｓｔｒｙ，２００５，７７（１４）：４６２６—

４６３９．

［１９］ＵＥＮＧ Ｓ Ｚ，ＬＡＴＨＡＲＡ Ｍ，ＢＡＧＨＳＯＲＫＨＩ Ｓ Ｓ，ｅｔ ａ１．ＣＵＤＡ—ｌｉｔｅ：ｒｅ．

ｄｕｃｉｎｇ ＧＰＵ ｐｒｏｇｒａｍｍｉｎｇ ｃｏｍｐｌｅｘｉｔｙ：ｌｎｇｕａｇｅｓａ ａｎｄ ｃｏｍｐｉｌｅｒｓ ｆｏｒ ｐａｒ－

Ｐｒｏｅ ｏｆ Ｇｅｒｍａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ．２００９：６７．７９．

ｌｌａｅｌ ｃｏｍｐｕｔｉｎｇ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ２ｈｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ．２００８：

１—１５． ，

［９］李博，刘国峰，刘洪．地震叠前时间偏移的一种图形处理器提速

实现方法［Ｊ］．地球物理学报，２００９，５２（１）：２４５．２５２．

［１０］张庆丹，戴正华，冯圣中，等．基于ＧＰＵ的串匹配算法研究［Ｊ］．

计算机应用，２００６，２６（７）：１７３５—１７３７．

［２Ｏ］邓仰东．ＮＶＩＤＩＡ ＣＵＤＡ超大规模并行程序设计训练课程：性能

提升［ＥＢ／ＯＬ］．（２００９）［２０１０・０３—１１］．ｈｔｔｐ：／／ｅｕｄａ．ｅｓｄｎ．ｎｅｔ／

Ｃｌｉｅｎｔ／ＣＵＤＡ ｌｅｃｔｕｒｅ．ｒａｒ．

（上接第３４０５页）加，系统Ｔｏｐ—ｎ查准率均不断下降，反映了结果

ｈａｖｉｏｒ：Ｇｏｏｇｌｅ ｍｏｂｉｌｅ ｓｅａｒｃｈ［ｃ］／／Ｐｒｏｃ ｏｆ ＳＩＧＣＨＩ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ

Ｈｕｍａｎ Ｆａｃｔｏｒｓ ｉｎ Ｃｏｍｐｕｔｉｎｇ Ｓｙｓｔｅｍｓ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ。２０ｏ６：

７Ｏ１．７０９．

的紧前趋势。个性化系统具有相对更高的查准率，表明本系统

相关结果排名更趋于靠前，实现了系统设计的目标。

Ｏ

［２］ＨＡＶＥＬＩＷＡＬＡ Ｔ Ｈ＿Ｔｏｐｉｃ—ｓｅｎｓｉｔｉｖｅ ｐａｇｅ ｒａｎｋ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ｌｌｔｈ

Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｅｅ ｏｎ Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ，

２００２ １５ｌ７－５２６．

得Ｏ

。

霸０

０

［３］吴晓，李丹宁，林洁．个性化搜索引擎中用户兴趣模型的研究

［ｃ］／／ｇ三届全国信息检索与内容安全学术会议论文集．２００７：

８２９—８３２．

＿标准－十性化

◆ 标准一个性化

图３平均查准率

图４ Ｔｏｐ一 查准率

［４］ＬＩＵ Ｆ，Ｙｕ Ｃ，ＭＥＮＧ Ｗｅｉ－ｙｉ．Ｐｅｒｓｏｎａｌｉｚｅｄ Ｗｅｂ ｓｅａｒｃｈ ｆｏｒ ｉｍｐｒｏｖｉｎｇ

ｒｅｔｉｒｅｖａｌ ｅｆｆｅｃｔｉｖｅｎｅｓｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎ￥ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ

Ｅｎｇｉｎｅｅｒｉｎｇ，２００４，１６（１）：２８—４０．

４结束语

由于移动用户的应用特点，对信息的精确获取和排序成为

了一个需要重点解决的问题。本文设计了一个个性化的移动

搜索模型，与其他模型相比，它有两方面的优势：更细粒度的兴

趣映射和基于反馈机制的本体概念描述。最后设计了相应的

实验，其结果表明，本文的系统在查全率和查准率上都有较大

的提升。 ‘

参考文献：

［１］ＫＡＭＶＡＲ Ｍ，ＢＡＬＵＪＡ Ｓ．Ａ ｌａｒｇｅ ｓｃａｌｅ ｓｔｕｄｙ ｏｆ ｗｉｒｅｌｅｓｓ ｓｅａｒｃｈ ｂｅ—

［５］ＶＡＲＭＡ Ｖ，ＳＲＩＨＡＲＳＨＡ Ｎ，ＰＩＮＧＡＬＩ Ｐ，ｅｔ ａ１．Ｐｅｒｓｏｎａｌｉｚｅｄ Ｗｅｂ

ｓｅａｒｃｈ ｅｎｇｉｎｅ ｆｏｒ ｍｏｂｉｌｅ ｄｅｖｉｃｅｓ［Ｃ］／／Ｐｒｏｅ ｆｏ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ

ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｉｎｆｏｒｍａｔｉｏｎ Ａｃｃｅｓｓ．２ｏｏ６．

［６］ＳＩＥＧ Ａ，ＭＯＢＡＳＨＥＲ Ｂ，ＢＵＲＫＥ Ｒ．Ｏｎｔｏｌｏｇｉｃａｌ ｕｓｅｒ ｐｒｏｆｉｌｅｓ ｆｏｒ

ｐｅｒｓｏｎａｌｉｚｅｄ Ｗｅｂ ｓｅａｒｃｈ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ５ｔｈ Ｗｏｒｋｓｈｏｐ ｏｕ Ｉｎｔｅｌｌｉ—

ｇｅｎｔ Ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ Ｗｅｂ Ｐｅｍｏｎａｌｉｚａｔｉｏｎ．２００７．

［７］ＧＡＵＣＨ Ｓ，ＣＨＡＦＦＥＥ Ｊ，ＰＲＥＴＳＣＨＮＥＲ Ａ．Ｏｎｔｏｌｏｇｙ－ｂａｓｅｄ ｐｅｒｓｏｎａ．

１ｉｚｅｄ ｓｅａｒｃｈ ａｎｄ ｂｒｏｗｓｉｎｇ［Ｊ］．Ｗｅｂ Ｉｎｔｅｌｌｉｇｅｎｃｅ ａｎｄ Ａｇｅｎｔ Ｓｙｓ－

ｔｅｒｎｓ，２ｏｏ３，１（３—４）：２１９－２３４．

2023年10月10日发(作者：x疾病)

第２７卷第９期

２０１０年９月

计算机应用研究

Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ

Ｖ０１．２７ Ｎｏ．９

Ｓｅｐ．２０１０

基于ＣＵ ＤＡ的蛋白质翻译后修饰鉴定

ＭＳ・－Ａｌｉｇｎｍｅｎｔ 算法加速研究

翟艳堂 ，涂强 ，郎显宇 ，陆忠华 ，迟学斌

（１．中国科学院计算机网络信息中心超级计算中心，北京１００１９０；２．中国科学院研究生院，北京１０００４９）

摘要：对ＭＳ—Ａｌｉｇｎｍｅｎｔ算法进行分析得出该算法很难满足大规模数据对鉴定速度的要求，而且具有的一个特

点是相同的任务在不同的数据上重复计算，为数据划分提供了基础。基于ＣＵＤＡ编程模型使用图形处理器

（ＧＰＵ）对步骤数据库检索及候选肽段生成进行加速优化，设计了该步骤在单ＧＰＵ上的实现方法。测试结果表

明，此方法平均加速比为３０倍以上，效果良好，可以满足蛋白质翻译后修饰鉴定中大规模数据快速计算的需求。

关键词：蛋白质翻译后修饰鉴定；ＭＳ—Ａｌｉｇｎｍｅｎｔ；图形处理器；统一计算设备架构

中图分类号：ＴＰ３１２ 文献标志码：Ａ 文章编号：１００１—３６９５（２０１０）０９—３４０９ ０６

ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１—３６９５．２０１０．０９．０５６

Ｒｅｓｅａｒｃｈ ｏｆ ＣＵＤＡ．．ｂａｓｅｄ ａｃｃｅｌｅｒａｔｉｏｎ ｏｆ ＭＳ．．Ａｌｉｇｎｍｅｎｔ ｆｏｒ

ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ｏｆ ｐｏｓｔ—ｔｒａｎｓｌａｔｉｏｎａｌ ｍｏｄｉｉｃａｔｉｏｎｓ ｆ

ＺＨＡＩ Ｙａｎ—ｔａｎｇ ， ，ＴＵ Ｑｉａｎｇ ，ＬＡＮＧ Ｘｉａｎ—ｙｕ ，ＬＵ Ｚｈｏｎｇ—ｈｕａ ，ＣＨＩ Ｘｕｅ ｂｉｎ

（１．Ｓｕｐｅｒｃｏｍｐｕｔｉｎｇ Ｃｅｎｔｅｒ，Ｃｏｍｐｕｔｅｒ Ｎｅｔｗｏｒｋ Ｉｎｆｏｒｍａｔｉｏｎ Ｃｅｎｔｅｒ，Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆＳｃｉｅｎｃｅ，Ｂｅｉｊｉｎｇ １００１９０，Ｃｈｉｎａ；２．Ｇｒａｄｕａｔｅ Ｕｎｉｖｅｒｓｉｔｙ

ｆＣｈｉｎｅｓｅｏ Ａｃａｄｅｍｙ ｏｆＳｃｉｅｎｃｅ，Ｂｅｒｉｎｇ １０００４９，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｆｉｒｓｔｌｙ ａｎａｌｙｚｅｄ ＭＳ—Ａｌｉｇｎｍｅｎｔ．Ｉｔ ｃｏｕｌｄ ｎｏｔ ｗｅｌｌ ｍｅｅｔ ｔｈｅ ｃｈａｌｌｅｎｇｅ ｏｆ ｌａｒｇｅ ｓｃａｌｅ ｄａｔａ．Ｏｎｅ ｏｆ ｉｔｓ ｌｅａ—

ｔｕｒｅｓ ｗａｓ ｔｈｅ ｓａｍｅ ｃｏｍｐｕｔｉｎｇ ｏｐｅｒａｔｉｏｎｓ ｒｅｐｅａｔ ｏｎ ｄｉｆｆｅｒｅｎｔ ｄａｔａ．Ｔｈｉｓ ｆｅａｔｕｒｅ ｐｒｏｖｉｄｅｄ ｂａｓｅ ｆｏｒ ｄａｔａ ｐａｒｔｉｔｉｏｎ．Ｔｈｉｓ ｐａｐｅｒ ｔｈｅｎ

ｕｓｅｄ ＧＰＵ（ｇｒａｐｈｉｃｓ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔｓ）ｔｏ ａｃｃｅｌｅｒａｔｅ ｔｈｅ ｓｔｅｐ ｏｆ ｄａｔａｂａｓｅ ｓｅａｒｃｈ ａｎｄ ｃａｎｄｉｄａｔｅ ｇｅｎｅｒａｔｉｏｎ．Ａｎｄ ｉｔ ｐｒｅｓｅｎｔｅｄ ａｎ

ｏｐｔｉｍｉｚｅｄ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ＣＵＤＡ（ｃｏｍｐｕｔｅ ｕｎｉｉｆｅｄ ｄｅｖｉｃｅ ａｒｃｈｉｔｅｃｔｕｒｅ）ｐｒｏｇｒａｍｍｉｎｇ ｍｏｄｅｌ ｏｎ ｓｉｎｇｌｅ ＧＰＵ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎ—

ｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ａｖｅｒａｇｅ ｓｐｅｅｄｕｐ ｒａｔｉｏ ｉｓ ｍｏｒｅ ｔｈａｎ ３０，ａｎｄ ｔｈｅ ｍｅｔｈｏｄ ｅｆｆｅｃｔｉｖｅｌｙ ｉｍｐｒｏｖｅｓ ｉｄｅｎｔｉｉｃａｔｉｆｏｎ ｓｐｅｅｄ ａｎｄ ｉｓ

ａｐｐｌｉｃａｂｌｅ ｆｏｒ ｌａｒｇｅ ｓｃａｌｅ ｄａｔａ ｒｅｑｕｉｒｉｎｇ ｆｏｒ ｈｉｇｈ—ｓｐｅｅｄ ｐｒｏｃｅｓｓｉｎｇ．

Ｋｅｙ ｗｏｒｄｓ：ｉｄｅｎｔｉｉｆｃａｔｉｏｎ ｏｆ ｐｏｓｔ—ｔｒａｎｓｌａｔｉｏｎａｌ ｍｏｄｉｉｆｃａｔｉｏｎｓ；ＭＳ—Ａｌｉｇｎｍｅｎｔ；ｇｒａｐｈｉｃｓ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔｓ（ＧＰＵ）；ｃｏｍｐｕｔｅ

ｕｎｉｆｉｅｄ ｄｅｖｉｃｅ ａｒｃｈｉｔｅｃｔｕｒｅ（ＣＵＤＡ）

在生物信息学领域逐渐成为发展趋势，一些研究工作取得了全

０ 引言

研究蛋白质翻译后修饰（ｐｏｓｔ—ｔｒａｎｓｌａｔｉｏｎａｌ ｍｏｄｉｉｆｃａｔｉｏｎｓ）是

新进展，产生了一些基于ＧＰＵ的软件 ’“ 。

由于从基本的图形设备发展到高度并行化的多线程多核

处理器，ＧＰＵ主要用于数据处理而非数据缓存和流控制，非常

适合于计算密集型、高度数据并行化的计算 ” 。本文对

理解各种细胞调节过程的关键，对阐明蛋白质的功能具有重要

作用 。ＭＳ—Ａｌｉｇｎｍｅｎｔ算法是一种非限制性的蛋白质翻译后

修饰鉴定算法，其优点在于卣搜索：在不知道样本中存在哪些

ＭＳ—Ａｌｉｇｎｍｅｎｔ算法进行分析，得出该算法的一个特点是相同的

计算任务在大量数据上重复计算，其为数据并行提供了基础。

ＮＶＩＤＩＡ公司发布的ＣＵＤＡ（ｃｏｍｐｕｔｅ ｕｎｉｉｆｅｄ ｄｅｖｉｃｅ ａｒｃｈｉｔｅｃｔｕｒｅ，

统一计算设备架构）是一种并行编程模型，能促使ＧＰＵ发挥并

行计算的优势，ＣＵＤＡ是Ｃ编程语言的扩展，编程简单，入门容

易 川。本文选择ＣＵＤＡ编程模型设计该算法的关键步骤

翻译后修饰类型的情况下利用串联质谱检索蛋白质序列数据

库，还可以发现一些未知的翻译后修饰 “。。但是ＭＳ—Ａｌｉｇｎ—

ｍｅｎｔ鉴定速度较慢，很难满足快速增长的实验质谱数据和蛋

白质数据库 对提高鉴定速度的要求 。

高性能计算的发展对提升速度做出了巨大贡献。从２００３

即数据库检索及候选肽段生成在ＧＰＵ上的实现方法，并总结

一

年开始，ＧＰＵ（ｇｒａｐｈｉｃｓ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔｓ）就在浮点运算性能和存

储器带宽上将￣ＣＰＵ抛在其后￣７，８ ３，在功耗和成本上也优势明

显 ，而且随着ＧＰＵ上可编程性的增强，ＧＰＵ突破仅用于图形

领域的局限，开始用于一些通用计算 ’ 。ＧＰＵ高性能计算

收稿日期：２０１０．０３．１１；修回日期：２０１０．０４—１２ 基金项目：中国科学院知识创新工程重大项目基金资助项目（ＫＧＧＸ１一Ｙｗ－１３）；ＣＮＩＣ主

些ＧＰＵ优化技巧，最终对其结果进行分析。将ＧＰＵ计算技

术应用于ＭＳ—Ａｌｉｇｎｍｅｎｔ算法的提速是可行的，取得了３０倍以

上的加速比。

ＣＵＤＡ是ＮＶＩＤＩＡ公司发布的用于ＮＶＩＤＩＡ ＧＰＵ上的通用

任基金资助项目（ＣＮＩＣ—ＺＲ ０９００５）；财政部国家重大科研装备研制项目（ＺＤＹＺ２００８－２）；中国科学皖院长奖获得者科研专项基金资助

作者简介：翟艳堂（１９８４．），男，江苏徐州人，硕士，主要研究方向为并行计算（ｚｙｔ０３０３＠１６３．ｃｎ）；涂强（１９８４一），男，工程师，硕士，主要研究方向

为并行计算；郎显宇（１９７９．），女，助研，博士，主要研究方向为生物信息与并行计算；陆忠华（１９６５一），女，研究员，博士，主要研究方向为生物数学与

并行计算；迟学斌（１９６３一），男，研究员，博士，主要研究方向为网格计算、并行计算与软件．

・

３４１０・ 计算机应用研究 第２７卷

并行编程模型，是Ｃ编程语言的扩展 川。使用ＣＵＤＡ编程

时，ＣＰＵ被作为主机（ｈｏｓｔ），ＧＰＵ被作为主机的协处理器（ＣＯ—

ｐｒｏｃｅｓｓｏｒ），被看做执行高度线程化并行处理任务的计算设备

（ｄｅｖｉｃｅ）。运行在ＧＰＵ上的ＣＵＤＡ并行计算函数称为内核

情况（简称Ｍｏｄ＝３＋）。不同的情况计算匹配的方法有所不

同。

本文主要研究的是Ｍｏｄ＝２的情况，对于其他情况亦可借

鉴本文ＧＰＵ加速方法，本文暂不讨论。

输入：一张实验质谱

预处理

Ｔａｇ２￣成

（ｋｅｒｎｅ１），以线程栅格（ ｄ）的形式组织，线程栅格由若干个线

程块（ｂｌｏｃｋ）组成，每个线程块又由若干个线程（ｔｈｒｅａｄ）组成。

使用ｎｖｃｃ编译器编译ＣＵＤＡ源文件，ｋｅｍｅｌ将被编译成设备端

指令。在实际运行中，线程块会被分割为更小的线程束

（ｗａｒｐ），线程束作为真正的执行单位。线程束的大小由硬件的

取数据库中一条蛋白质序列

』

计算该蛋白质序列的任意候选

肽段与实验质谱的匹配分数

输入：一个蛋自质数据库

数据库检索及候选肽段生成 若该分数大于最优匹配分数

还有蛋白质

、、

——

—— —

』

则更新最优匹配

计算能力版本决定，在采用Ｔｅｓｌａ架构的ＧＰＵ中，一个线程束

由连续的３２个线程组成。ＧＰＵ有自己的存储器，称为设备存

储器（ｄｅｖｉｃｅ ｍｅｍｏ￣），相对于ＣＰＵ的主机存储器（ｈｏｓｔ ｍｅｍｏ—

ｒｙ）。ＣＵＤＡ规定了如下的存储器模型：每个线程拥有自己的

一

否

Ｐ埴计算

—

寄存器（ｒｅｇｉｓｔｅｒ）和局部存储器（１ｏｃａｌ ｍｅｍｏ￣）；每个线程块拥

有一块共享存储器（ｓｈａｒｅｄ ｍｅｍｏ￣）；线程栅格中的所有线程

均可以访问全局存储器（ｇｌｏｂａｌ ｍｅｍｏ￣）；所有线程可只读访问

的两种存储器，即常数存储器（ｃｏｎｓｔｌｆＹｌｔ ｍｅｍｏ￣）和纹理存储器

（ｔｅｘｔｕｒｅ ｍｅｍｏ￣）。

上～

否还有实验

输出：最优修饰肽段

一

Ｊ输出最优修饰肽段ｊ

肽段生成主要流程

图１ ＭＳ—Ａｌｉｇｎｍｅｎｔ主要流程

图２数据库检索及候选

Ｍｏｄ＝２的计算匹配方法定义一个ＩＰＩ Ｘ ｆＮｏｄｅｓＩ的矩

１ ＭＳ—Ａｌｉｇｎｍｅｎｔ算法

１．１ 修饰肽段鉴定问题

阵Ｄ７－。其中：Ｐ是蛋白质数据库中某条蛋白质序列，Ｎｏｄｅｓ是

质谱谱峰的集合。

矩阵中每个元素看做是一个节点（ｎｏｄｅ），沿矩阵准对角

线方向构建有向路径，路径上的节点是矩阵的元素（ ， ），边的

起点（ｉ， ）和终点（ ，，）满足ｉ≤ 且 ≤，，某个节点处的分数

符号定义１ Ａ＝｛ａ 一，ａ 。｝代表２０种氨基酸的集合，

ｍａｓｓ（ａ ）代表氨基酸的分子质量。

符号定义２ Ｐ＝ｐ。…Ｐ 代表肽段序列，Ｐ ∈Ａ，其质量为

ｍａｓｓ（Ｐ）＝ ｍａｓｓ（Ｐ ）

代表到达该节点路径的分数。对于矩阵中尚未计算分数的某

点（ｉ， ），以一条最佳（分数最高）的边与已计算分数的某点

（ｉ…，Ｌ ）建立联系而拓展路径，该边的起点和终点分别是

（ｉ…，Ｊｐ ）和（ｉ， ）。

Ｐ在氨基酸Ｐ 处发生修饰变成修饰肽段Ｐ，质量变为ｍａｓｓ

（Ｐ）＋△，△是质量差。

矩阵中某条路径的分数加上某个后缀的分数及位点处的

修饰分数即为某肽段与质谱的匹配分数，当此分数满足一定的

条件时，该路径上的氨基酸和该后缀及位点处的修饰构成的肽

段即为候选肽段。

符号定义３ Ｓ代表实验质谱，其母离子质量ＰＭ等于产

生该质谱的肽段的质量。

符号定义４ ｐｒｅｆｉｘｓｅｏｒｅ（Ｐ ， ）（ｉ≤ ）是肽段前缀Ｐ …Ｐ

打分函数，ｓｕｆｉｆｘｓｃｏｒｅ（ｐ ｐ ）（ｉ ≤ ）是肽段后缀Ｐ ，…ｐ，，打分

函数，ｐｔｍｓｃｏｒｅ（Ａ，Ｐ ）是氨基酸Ｐ 位点处发生修饰△打分函

数，ｓｃｏｒｅ（）代表其他打分函数。

符号定义５ ＤＢ代表蛋白质数据库，其中肽段最多发生

次修饰产生的任意修饰肽段称为候选肽段ｐ，具有最佳匹配分

数的候选肽段称为最优修饰肽段Ｐ 。

修饰肽段鉴定问题（ｍｏｄｉｉｆｅｄ ｐｅｐｔｉｄｅ ｉｄｅｎｔｉｉｆｃａｔｉｏｎ ｐｒｏｂ—

ｌｅｍ）Ｌ２ Ｊ输入：蛋白质数据库ＤＢ，实验质谱Ｓ，修饰发生的次数

候选肽段Ｐ ，…Ｐｊ（ｉ ≤ ＜ ）与质谱的匹配分数为

Ｄ：Ｄ Ｐ ， ）＋ｓｕｆｉｆｘｓｃｏｒｅ（ｐ ＋１，ｐ ） ｐｔｍｓｅｏｍ（Ａ，Ｐ ＋１） （１）

其中：Ｐ ∈Ｐ，ｎ ∈Ｎｏｄｅｓ；ｍｉｎ￣≤△≤ｍａ】（△，ｒｎｉｎ￣、ｍａｘＡ分别为修

饰质量差的最小值和最大值。

矩阵中某点的分数：

ＤＴ（ｐ ，ｎ ）＝ｓｃｏｒｅ（ｍａｓｓ（ｎ＾））＋ｂｅｓｔｓｃｏｒｅ （２）

其中：

ｂｅｓｔｓｃｏｒｅ＝ｍａｘ｛

初始值：ｓｔａｒｔｓｃｏｒｅ（ｐ ）；

；输出：最优修饰肽段 。

１．２ ＭＳ—Ａｌｉｇｎｍｅｎｔ（Ｍｏｄ＝２）算法描述

ＭＳ—Ａｌｉｇｎｍｅｎｔ算法主要由预处理（ｐｒｅｐｒｏｃｅｓｓｉｎｇ）、Ｔａｇ生成

（Ｔａｇ ｇｅｎｅｒａｔｉｏｎ）、数据库检索及候选肽段生成（ｄａｔａｂａｓｅ ｓｅａｒｃｈ

＆ｃａｎｄｉｄａｔｅ ｇｅｎｅｒａｔｉｏｎ）和Ｐ值计算（Ｐ—ｖａｌｕｅ ｃｏｍｐｕｔａｔｉｏｎ）几个

／ｎａｘ｛Ｄ Ｐ ，ｅｄｇｅ．ｔｏｎｏｄｅ）＋ｓｃｏｒｅ（ｅｄｇｅ）Ｉ ｅｄｇｅ∈｛ｎ 向后跨度

ｍａｓｓ（ ）的边｝｝；

ｍａｘ｛ＤＴ（ｐＨ，ｅｄｇｅｄｏｕｂｌｅ．ｔｏｎｏｄｅ）＋ｓｃｏｒｅ（１／２ｍａｓｓ（ｅｄｇｅｄ０ｕｂｌｅ））＋

ｓｃｏｒｅ（ｅｄｇｅｄｏｕｂｌｅ）Ｉ ｅｄｇｅｄｏｕｂｌｅ∈｛ 向后跨度ｍａｓｓ（ｐＨＰｒ）的边｝ｌ；

ｍａｘ｛Ｄｒ（ｐ 一３，ｅｄｇｅｔｒｉｐｌｅ．ｔｏｎｏｄｅ）＋ｓｃｏｒｅ（Ｉ／３ｍａｓｓ（ｅｄｇｅｔｒｉｐｌｅ））＋

步骤组成，如图１所示。数据库检索及候选肽段生成是其关键

步骤，如图２。计算蛋白质序列的任意候选肽段与实验质谱的

匹配分数（简称计算匹配，下同）是数据库检索部分的重要部

分 。Ｍｓ－Ａｌｉｇｎｍｅｎｔ依据限定修饰发生的次数分成三个模

块，即最多有一个翻译后修饰情况（简称Ｍｏｄ＝１）、最多有两

ｓｃｏｒｅ（２／３ｍａｓｓ（ｅｄｇｅｔｒｉｐｌｅ））＋ＳＣＯＩＤ（ｅｄｇｅｔｒｉｐｌｅ）ｌ ｅｄｇｅｔｒｉｐｌｅ∈｛ 向后跨

度ｍａｓｓ（ｐ ２Ｐ Ｐ ）的边｝｝；

ｍａｘ｛Ｄ Ｐ ，，ｎ０）＋ｐｒｅｆｉｘｓｃｏｒｅ（ｐ Ｐ ）１０＜ｉ ≤ｉ｝；

ｍａｘ｛ＤＴ（ｐ ，，Ｈｏ）＋ｐｒｅｆｉｘｓｃｏｒｅ（ｐ 一，Ｐ ）＋ｐｔｍｓｅｏｒｅ（Ａ，Ｐ ）１０＜ｉ ≤ｉ，

ｍｉｎＡ≤△≤ｍａ）【△｝：

｝

１．３ ＭＳ—Ａｌｉｇｎｍｅｎｔ（Ｍｏｄ＝２）算法性能分析

对ＭＳ—Ａｌｉｇｎｍｅｎｔ（Ｍｏｄ＝２）算法进行分析得出其计算时间

个翻译后修饰情况（简称Ｍｏｄ＝２）和最多有多个翻译后修饰 复杂度为０（ ・ ・ｍ ・ｍ ・Ｍｊ）。其中： 为实验质谱的

第９期 翟艳堂，等：基于ＣＵＤＡ的蛋白质翻译后修饰鉴定ＭＳ—Ａｌｉｇｎｍｅｎｔ算法加速研究 ・３４１１・

２．１．２使用ＧＰＵ加速的可行性

数量， 为蛋白质数据库中蛋白质序列条数，ｍ 是蛋白质序

列长度，即构成该蛋白质的氨基酸个数，ｍ 是质谱谱峰数，

是修饰质量差跨度。然后进行实际数据测试，测试使用的实验

质谱由中国科学院上海生命科学研究院盛泉虎博士提供；蛋白 个特点是相同的计算任务在不同的数据上重复计算，此特点

质数据库采用ｉｐｉ．ＭＯＵＳＥ．ｖ３．２９．ＲＥＶＥＲＳＥＤ（１０７ ９６２条蛋白

质序列）由盛泉虎博士提供，ｕｎｉｐｒｏｔ—ｓｐｒｏｔ（４６６ ７３９条蛋白质序 质序列划分成一个个小肽段，是一种细粒度的数据划分。

列）来源于ＥＭＢＬ—ＥＢＩ（Ｅｕｒｏｐｅａｎ Ｍｏｌｅｃｕｌａｒ Ｂｉｏｌｏｇｙ Ｌａｂｏｒａｔｏｒｙ— ＭＳ—Ａｌｉｇｎｍｅｎｔ（Ｍｏｄ＝２）移植到ＧＰＵ上之后，ＧＰＵ上不同

Ｅｕｒｏｐｅａｎ Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ Ｉｎｓｔｉｔｕｔｅ，欧洲分子生物学实验室暨欧洲

生物信息学中心）。

对ＭＳ—Ａｌｉｇｎｍｅｎｔ（Ｍｏｄ＝２）算法分析可得其计算任务在不

同的实验质谱、不同的蛋白质序列上重复计算，因此该算法的

一

为数据并行提供了基础。对蛋白质数据库进行划分，是将蛋白

的线程采用相同的任务处理不同的数据，之间数据相关性比较

小而且不复杂，可以采取ＣＵＤＡ提供的通信机制 和编程者

采取其他方法有效解决。

２．２ ＤＣＧＰＵＭ ２算法描述

在表１所列的环境１下，统计了该算法在输入不同质谱数

量和不同规模蛋白质数据库的情况下的计算时间，如图３所

示；采用文献［６］的程序统计了在环境３集群上的计算时间如

图４所示。

表ｌ硬件环境

环境 硬件配置

ｌ ＣＰＵ：ＡＭＤ Ｐｈｅｎｏｍ ９８５０ ２．５ ＧＨｚ；Ｍｅｍｏｒｙ：８ ＧＢ

ＣＰＵ：Ｉｎｔｅｌ Ｘｅ。“Ｅ５４１０ ２・３３ ＧＨ ；Ｍ ｍ。ｒｙ：８ ＧＢ；

ＧＰＵ：ＮＶＩＤＩＡ Ｔｅｓｌａ Ｃ１０６０ １．４４ ＧＨｚ：Ｃｏｍｐｉｌｅｒ：ｎｖｃｃ ２ ２

Ｃｌｕｓｔｅｒ：１８个计算节点，每个节点配置一颗ｌｎｔｅｌ Ｘｅｏｎ

３

Ｅ５４１０四核处理器，２ ３３ ＧＨｚ，８ ＧＢ内存

３

２

１

１

‘＝１

ｓｐｅｃｔｒａ ｓｅａｒｃｈｅｄ ｓｐｅｃｔｒａ ｓｅａｒｃｈｅｄ

图３ ＭＳ—Ａｌｉｇｎｍｅｎｔ（Ｍｏｄ：２） 图４ Ｍｓ—Ａ１ｉｇｎｍｅｎｔ（Ｍ０ｄ＝２）

ＣＰＵ串行执行时间 在ｃｌｕｓｔｅｒ上的执行时间

进一步对算法各步骤计算时间占整个计算时间的比重进

行统计分析，得到步骤数据库检索及候选肽段生成的计算时间

占９９．９％以上。因此，如果能降低此部分的计算时问，则整个

流程的计算时间就能有效地减少。

２ ＧＰＵ加速算法ＤＣＧＰＵＭ ２

２．１ ＭＳ—Ａｌｉｇｎｍｅｎｔ（Ｍｏｄ＝２）使用ＧＰＵ加速的原因和可行性

２．１．１ 使用ＧＰＵ加速的原因

ＧＰＵ的设计能使更多晶体管用于数据处理而非数据缓存

和流控制，特别适合于计算密集型、高度数据并行化的计

算 。众多的处理核心（如ＮＶＩＤＩＡ Ｔｅｓｌａ Ｃ１０６０有２４０个处

理核心）使数据细粒度并行化更高。

ＭＳ．Ａｌｉｇｎｍｅｎｔ需要两种数据，即实验质谱和蛋白质数据

库。而且数据量较大、计算时间长。根据图３的增长趋势，当

实验质谱有５０ ０００张、蛋白质数据库采用ｉｐｉ．ＭＯＵＳＥ．ｖ３．２９．

ＲＥＶＥＲＳＥＤ时 鉴定时间可达２６ ７１５ ｈ（３年左右）；蛋白质数

据库采用ｕｎｉｐｒｏｔ—ｓｐｒｏｔ时，鉴定时间可达９４ ４３２ ｈ（１０年左

右），在集群上也可达２ ７７０ ｈ（３．８５个月左右）。当质谱数量

和数据库规模较大时，算法不能很好地满足鉴定速度的要求，

需要采用高性能计算加速鉴定过程。可对上述两种数据进行

划分，即实验质谱是粗粒度数据并行；蛋白质数据库是细粒度

数据并行。在划分质谱的基础上进一步对蛋白质数据库进行

划分可带来更高的加速效果，而对蛋白质数据库的细粒度数据

并行适合采用ＧＰＵ处理。

借鉴加利福尼亚大学圣地亚哥分校计算质谱中心（Ｃｅｎｔｅｒ

ｆｏｒ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｍａｓｓ Ｓｐｅｃｔｒｏｍｅｔｒｙ，Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｃａｌｉｆｏｒｎｉａ，Ｓａｎ

Ｄｉｅｇｏ）实现ＭＳ—Ａｌｉｇｎｍｅｎｔ算法的代码，设计数据库检索及候选

肽段生成在单ＧＰＵ上实现的算法ＤＣＧＰＵＭ２（ｄａｔａｂａｓｅ ｓｅａｒｃｈ

ａｎｄ ｃａｎｄｉｄａｔｅ ｇｅｎｅｒａｔｉｏｎ ｕｓｉｎｇ ＧＰＵ ｆｏｒ Ｍｏｄ＝２）。数据划分的

方法如下：将数据库中所有的蛋白质序列看成一整条序列；将

该序列划分成等长的序列段依次用ＧＰＵ处理；在ＧＰＵ内，将

序列段划分到多个线程块上；在线程块内，将序列段划分成更

小的序列段分配到多个线程，线程之间共享一部分小序列片

段，具体如图５所示。ＤＣＧＰＵＭ２主要流程如图６所示。将蛋

＼、¨

白质数据库中的所有序列看成一条序列ＰＷ。

…………＿●

ＧＰＵ ＧＰＵ ＧＰＵ ＧＰＵ

翟

，

，

、

。

＿・

ｔｈｒｅａｄ ｔｈｔ：ｅａｄ

图５ ＤＣＧＰＵＭ２数据划分方式 图６ ＤＣＧＰＵＭ２主要流程

第一个内核：ｋｅｒｎｅｌｌ。每个线程计算以序列ＰＷ的氨基

酸Ｐ 开始长度为３２的肽段Ｐ＝Ｐ …Ｐ 中每个前缀ＰⅢ 的质

量和分数，并且Ｐ。 也是以Ｐ 作为开始氨基酸。其结果存储

在全局存储器空间。

第二个内核：ｋｅｍｅ￣。每个线程计算以序列ＰＷ的氨基酸

ｐ ，结束长度为３２的肽段Ｐ：ｐ …Ｐ ，中每个后缀Ｐ 的质量

和分数，并且Ｐ 也是以Ｐ 作为结束氨基酸。其结果存储在

全局存储器空间。

第三个内核：ｋｅｒｎｅｌ３。采用式（２）动态规划地填充表Ｄ

每个线程填充一列，在计算表中每个元素值时，考虑前缀处发

生一次修饰，而且与ＤＴ左上角的某些值具有数据相关性，如

图７所示。因为不同线程之间具有数据相关性，在填充一个元

素之后需要全局同步，如图８所示。

第四个内核：ｋｅｒｎｅｌ４。遍历ＤＴ表，查找候选肽段。每个

线程遍历一列，遍历到表中每个元素时，考虑后缀处发生一次

修饰。

２．３算法实现优似

存储器带宽是计算机性能的瓶颈之一，在以运算为主的

ＣＵＤＡ程序中，应尽量避免让存储器访问和通信成为性能瓶

颈；而在以存储器访问为主的应用中，应尽可能增大程序的可

・

３４１２・ 计算机应用研究 第２７卷

用带宽 。每种存储器的高效带宽较大程度地依赖于存储器

（ｃｏａｌｅｓｃｅｄ ａｃｃｅｓｓ），而且使用共享存储器不出现存储体冲突，

不出现使用共享存储器过多而造成线程块并发性降低或ｋｅｒ－

的访问模式 ”， ］，实现存储器的最大可用带宽是ＣＵＤＡ程序

优化的重要任务之一 。 ｎｅ】启动失败 等等。如果不出现存储体冲突，访问共享存储

图７填充Ｄ ７－表数据相关性 图８全局同步

１）全局同步（ｇｌｏｂａｌ ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ）

２．２节中提到采用动态规划的方式填充表ＤＴ，在计算表

中每个元素值时，与ＤＴ左上角的某些值具有数据相关性。这

样不同的线程之间具有数据相关性，而且跨线程块的线程之间

具有数据相关性，因此在填充一个元素之后需要全局同步。

ＣＵＤＡ提供的ｋｅｒｎｅｌ函数内同步指令有：ｓｙｎｃｔｈｒｅａｄｓ（）、

ｔｈｒｅａｄｆｅｎｅｅ

—

ｂｌｏｃｋ（）、一ｔｈｒｅａｄｆｅｎｃｅ（），前两者是线程块内同步，

后者可用于全局同步” ；启动ｋｅｒｎｅｌ也可以作为全局同步

点 』。两种方法均可以用于本文：ｋｅｒｎｅｌ函数内循环运算，采

用一ｔｈｒｅａｄｆｅｎｃｅ（）函数全局同步；ｋｅｒｎｅｌ函数外循环运算，采用

启动ｋｅｒｎｅｌ作为全局同步点。经比较，后者比前者性能提升

８．４６％左右（图９）。

２）使用分页锁定存储器（ｐａｇｅ—ｌｏｃｋｅｄ ｍｅｍｏ￣）

ＮＶＩＤＩＡ Ｔｅｓｌａ Ｃ１０６０通过ＰＣＩ Ｅ总线与主机端连接，一条

ＰＣＩ．Ｅ ２．０ １６ｘ总线的理论带宽是双向每向８ ＧＢｐｓ，远小于显

存和ＧＰＵ片上存储器带宽。ＰＣＩ—Ｅ总线带宽很容易成为整个

程序性能提升的瓶颈。使用分页锁定存储器的优势之一是主

机端与设备端之间的存储带宽较高 。使用分页锁定存储器

产生３２．３７％左右的性能提升（图９），性能提升在于主机端和

设备端数据传输部分。 不使用分页锁定存储器时，主机端向设

备端数据传输带宽为１．６３ ＧＢｐｓ，设备端向主机端数据传输带

宽为１．９４ ＧＢｐｓ；使用分页锁定存储器后，两者分别增至２．４７

ＧＢｐｓ和５．１１ ＧＢｐｓ。

３）使用纹理存储器（ｔｅｘｔｕｒｅ ｍｅｍｏ￣）

纹理存储器有缓存且对二维空间局域性缓存有优化，因此

访存性能较高 』，而且其空问比常数存储器空间大得多：在通用

计算中非常适合用于图像处理或查找表，对大量数据的随机访

问或非对齐访问也有良好的加速效果… 。本文ｋｅｒｎｅｌ函数中

要随机地查找一些表，而且只读，适合采用纹理存储器存储这些

表。质谱节点向后跨度一个氨基酸的表，在ｈｏｓｔ端代码中用链

表存储结构，使用指针数据类型，而在ｄｅｖｉｃｅ端代码ｋｅｒｎｅｌ函数

中不能再使用这种结构，而且在ｋｅｒｎｅｌ函数中对其只读。观察

此表，其具有稀疏矩阵的形态，采用行压缩格式存储在纹理存储

器空间，一些具有同样特点的表也采用这种方式存储。采用行

压缩存储格式能节省存储空间，采用纹理存储器是缘其优点。

使用纹理存储器带来约３Ｏ．９４％的性能提升（图９）。

４）使用共享存储器（ｓｈａｒｅｄ ｍｅｍｏｒｙ）及避免存储体冲突

（ｂａｎｋ ｃｏｎｆｌｉｃｔ）

使用共享存储器或充分使用共享存储器不是提高性能的

充要条件，但是如果ｋｅｒｎｅｌ函数的特点适合采用共享存储器则

可用之。例如，线程块内线程共享数据或通信，线程需要对全

局存储器空间多次访问或全局存储器访问不能构成联合访问

器几乎和访问寄存器一样快。本文的ｋｅｎｒｅｌ函数中不同的线

程共享一部分数据，而且这些数据存储在全局存储器中，因此

本文采用共享存储器在不同的线程之间共享数据而减少重复

频繁地访问全局存储器。共享存储器的元素类型占４ Ｂｙｔｅ，访

存索引与线程号对应，避免存储体冲突。使用共享存储器产生

４．９％左右的性能提升，如图９所示。

ｓｐｅｃｔｒｕｍ：ｈｉｓｔｏｎｅＦＴ

１．１０００３ １０００３．２ Ｊ １日增加时间

１２Ｏ

ｄａｔａｈ ＿ｌｌｎｉｎｒｏｔ ｓｎｒｎｔ Ｉ１矗优化后时间

１０Ｏ

８Ｏ

＿ｌ ］１ｉ

４．９％

６０

４０

７

７４．８７

２０

０

优化后ｋ… ｌ内循环 未使用分页 未使用 未使用

锁定存储器纹理存储器共享存储器

图９ ＧＰＵ优化性能提升

５）全局存储器联合访问（ｃｏａｌｅｓｃｅｄ ａｃｃｅｓｓ）

全局存储器访问延时是４００～６００时钟周期（ｃｌｏｃｋ ｃｙｃｌｅ），

而且不会被缓存，经常成为性能提升的障碍，因此采用正确的

访问模式来实现最大化的存储器带宽尤为重要。全局存储器

联合访问，即半ｗａｒｐ块中的线程进行的全局存储器访问可结

合成一个存储器事务时，全局存储器带宽的使用效率将达到最

高 。本文具体采用以下方式：

ａ）将氨基酸以字符（ｃｈａｒ）的形式存储，在全局存储器中占

８ ｂｉｔ；蛋白质的氨基酸序列顺序存储，不同的线程顺序访问序

列中的氨基酸，这样可构成全局存储器的联合访问。

ｂ）使用内嵌的数据类型ｉｎｔ２存储质量和分数，使用ｕｉｎｔ２

类型存储地址值，使不同的线程按顺序访问全局存储器。

ｃ）如果将申请的全局存储器空间看成逻辑二维表，则每

个线程按列访问，不同线程按行顺序访问 ，如图ｌ０所示。

３性能分析

采用１．３节中同样的实验质谱和蛋白质数据库；ＧＰＵ计

算环境为表１中的环境２，与其对比的是环境ｌ和３；环境３上

的并行程序采用文献［６］中的程序。

３．１加速比分析

统计了ＧＰＵ加速后整个流程的计算时间，如图１１所示。

根据图１１的增长趋势，当实验质谱有５０ ０００张、蛋白质数据

库采用ｉｐｉ．ＭＯＵＳＥ．ｖ３．２９．ＲＥＶＥＲＳＥＤ时，鉴定时间约需７５０ ｈ

（３１天左右），蛋白质数据库采用ｕｎｉｐｒｏｔ—ｓｐｒｏｔ时，鉴定时间约

需２ ５２５ ｈ（３．５１个月左右）。

由 甲 甲甲

…

一＿一一一一一一一一一

芷

＾［［圈…．．口图

；；；； ；；；； 喜

第９期 翟艳堂，等：基于ＣＵＤＡ的蛋白质翻译后修饰鉴定ＭＳ—Ａｌｉｇｎｍｅｎｔ算法加速研究 ・３４１３・

ＧＰＵ相对于集群１８个节点（７２颗处理器）的加速比分别如图 次传输的数据量。本文申请的全局存储器空间量约为７７

１２～１５。由图可见，输入不同质谱数量和不同蛋白质数据库规

模的情况下，单ＧＰＵ相对于单ＣＰＵ的加速比略有不同，核心 储器空间，循环处理ＤＣＧＰＵＭ２流程，每次使用不同块空问，最

函数的加速比略高于整个流程的加速比，但性能提升均在３０

倍以上，而且当数据库规模较大时，加速比在４１倍以上。

：：！： ！： ！ 翌 ！１２：！！＝！ ：！１

ｇ－４ｏ

＿８；ｓ髫 ３９． ， ９ｌ＿

３０

晏２ｏ

１０

０

ｓｐｅｃｔｒａ ｓｅａｒｃｈｅｄ

图１２数据库检索及候选肽段生成单ＧＰＵ相对于

单ＣＰＵ的加速比

呈

墓５０

ｗ

ｈ

ｏｌｅｆｌｏＳＥ．ｖ３２９．ＲＥＶＥＲＳＥＤ

ｗ

ＨＫｑｉｐｉ

ＭＯＵ

Ｄｕｎ

ｉ

ｐｒ￣ｔ－ｐｒ￣

ｓ

．．

４ｌ ３５ ４ｌ ９１ ４２．１

…

，１ ５５ ４ｌ ３７

｝４０

３０

姜２０

１０

０ Ｉ ＿Ｌ＿． ．ｉ． ＿＝ｉ。 ．０． Ｉ

１ ５ １０ ５０ １００

ｓｐｅｃｔｒａ ｓｅａｒｃｈｅｄ

图１ ３整个流程单ＧＰＵ相对于单ＣＰＵ的加速比

７ｌ ｌ４２ ２】３ ２８４ ３５５ ４２６ ４９７

ｓｐｅｃｔｒａ ｓｅａｒｃｈｅｄ

图１４整个流程单ＧＰＵ计算 图１５整个流程单ＧＰＵ相对于

时间与集群计算时间的比较 集群的加速比

ＤＣＧＰＵＭ２是对蛋白质数据库而不是质谱数据进行划分，

虽然不同质谱计算时问不一定相同，但当质谱数量较大时，整

个流程单ＧＰＵ计算时间与质谱数量大致呈正比关系，因此在

图１１和１４中，整个流程单ＧＰＵ计算时问增长方式大致呈线

性。由１．３节可知，整个流程单ＣＰＵ计算时间与质谱数量也

大致呈正比关系；数据库检索及候选肽段生成步骤的计算时间

与质谱数量也呈正比关系。因此，整个流程单ＧＰＵ相对于单

ＣＰＵ的加速比和数据库检索及候选肽段生成单ＧＰＵ相对于单

ＣＰＵ的加速比基本稳定，与质谱数量没有关系。

在图４和ｌ４中，整个流程在集群上的计算时间随质谱数

量的增加而增加，但不是正比关系。输入质谱数量不同的情况

下，负载平衡效率不同，最优情况是负载平衡效率为１００％，但

往往负载平衡效率不高。。Ｊ。之所以在图１５中，质谱数量为

４２６处所对应的加速比仅为０．９７，比图中其他值都小，是因为

质谱数量为４２６时，集群处理器负载平衡效率比其他处高，造

成集群计算时间与质谱数量的比率较低。

本文在算法实现上采用多种优化方法，得到了较高的加速

比，但笔者认为尚有进一步性能提升的空间，可以在以下方面

作进一步优化：

ａ）主机与设备之间的数据传输。主机与设备之间的数据

传输时间占ＤＣＧＰＵＭ２执行时间的３ｌ％以上，如图１６所示，减

少此部分时间对性能提升是有效的。可采用下面两种优化

途径：

（ａ）采用流操作，以期达到数据传输与内核执行之间异

步，减少程序执行时间。

（ｂ）整块数据传输而不是多次分小块传输 ，并且增大

一

ＭＢ，远小于Ｔｅｓｌａ Ｃ１０６０显存量。可以一次申请较大的全局存

后将整块数据一次传输。

ｂ）控制流指令。控制流指令一般会影响有效指令吞吐

量，降低ＧＰＵ程序执行性能 ，但是文献［１７］中提出：如果只

需要少量线程进行操作，使用类似“ｉｆ ｔｈｒｅａｄｌｄｘ＜Ｎ”的方式避

免多个线程同时运行占用更长时问。可采用下面两种优化

途径：

（ａ）修改控制条件，尽量避免在ｗａｒｐ内发生分支，如使控

制条件依赖于ｔｈｒｅａｄｌｄｘ／ｗａｒｐＳｉｚｅ（其中ｔｈｒｅａｄｌｄｘ为线程ＩＤ，

ｗａｒｐＳｉｚｅ为ｗａｒｐ大小） 。

（ｂ）循环展开，使用＃ｐｒａｇｍａ ｕｎｒｏｌｌ指令，或者编写程序时

不使用循环语句而直接将循环展开。

ｅ）ＧＰＵ加速算法。如果能在ＧＰＵ并行算法上进一步优

化，则性能提升空间将更大。

４０

ｇ ３０

量２０

奎１０

０

４结束语

本文在深入分析ＭＳ—Ａｌｉｇｎｍｅｎｔ（Ｍｏｄ＝２）算法的基础上，

总结该算法的特点，提出了该算法核心计算模块数据库检索及

候选肽段生成的单ＧＰＵ加速实现方法，总结了一些优化技巧，

针对不同情况采取相应的优化措施。测试结果表明，基于

ＧＰＵ的算法比ＣＰＵ上的串行算法提速明显，相对于集群也有

加速，可以满足大规模数据对鉴定速度的要求，ＧＰＵ高性能计

算在蛋白质翻译后修饰鉴定中的应用对计算蛋白质组学海量

数据处理提供了一种新的思路。ＧＰＵ用于并行计算及ＣＵＤＡ

编程具有优势，但也具有一些缺点。本文利用ＧＰＵ并行计算

的思想和优化的技巧可以被借鉴于蛋白质翻译后修饰鉴定其

他算法的加速优化和ＧＰＵ集群机器上的加速优化。ＭＳ—

Ａｌｉｇｎｍｅｎｔ算法是用实验质谱查询蛋白质数据库，鉴于此，可以

・

３４１４・ 计算机应用研究 第２７卷

将ＧＰＵ加速ＭＳ—Ａｌｉｇｎｍｅｎｔ的思想推广到基于质谱技术的计算

蛋白质组学的其他研究方面，如蛋白质鉴定（ｐｒｏｔｅｉｎ ｉｄｅｎｔｉｉｆｃａ—

ｔｉｏｎ）、氨基酸序列分析（ａｍｉｎｏ ａｃｉｄ ｓｅｑｕｅｎｃｅ ａｎａｌｙｓｉｓ）等，还可

［１１］ＮＶＩＤＩＡ Ｃｏｒｐｏｒａｔｉｏｎ．Ｔｅｓｌａ ＢＩＯ Ｗｏｒｋｂｅｎｃｈ一助力新型科学［ＥＢ／

ＯＬ］．［２０１０ ０３－１１］．ｈｔｔｐ：／／ｗｗｗ．ｎｖｉｄｉａ．ｅｎ／ｏｂｊｅｅｔ／ｔｅｓｌａ＿ｂｉｏ＿ｗｏｒｋ—

ｍ１． ｃｎ．ｈｔ

ｂｅｎｃｈ

—

以推广到其他领域，如蛋白质序列比对（ｐｒｏｔｅｉｎ ｓｅｑｕｅｎｃｅ ａｌｉｇｎ—

ｍｅｎｔ）、基因序列比对（ｇｅｎｅ ｓｅｑｕｅｎｃｅ ａｌｉｇｎｍｅｎｔ）等。

参考文献：

［１］ＮＡ Ｓ Ｊ，ＪＥＯＮＧ Ｊ Ｈ，ＰＡＲＫ Ｈ Ｊ，ｅｔ ａ１．Ｕｎｒｅｓｔｒｉｃｔｉｖｅ ｉｄｅｎｔｉｉｆｃａｔｉｏｎ ｏｆ

ｍｕｌｔｉｐｌｅ ｐｏｓｔ．．ｔｒａｎｓｌａｔｉｏｎａｌ ｍｏｄｉｉｆｃａｔｉｏｎｓ ｆｒｏｍ ｔａｎｄｅｍ ｍａｓｓ ｓｐｅｅｔｒｏｍｅ—

ｔｒｙ ｕｓｉｎｇ ａｎ ｅｒｒｏｒ—ｔｏｌｅｒａｎｔ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｆｉｎ ｅｘｔｅｎｄｅｄ ｓｅｑｕｅｎｃｅ

［１２］ＮＶＩＤ１Ａ Ｃｏｒｐｏｒａｔｉｏｎ．Ｔｅｓｌａ Ｂｉｏ Ｗｏｒｋｂｅｎｃｈ帮助科学家在生物科学

领域取得全新突破［ＥＢ／ＯＬ］．［２０１０—０３－１ １］．ｈｔｔｐ：／／ｗｗｗ．ｎｖｉｄｉａ．

ｃｎ／ｏｂｊｅｃｔ／ｉｏ—．１２６４４０５２４８４１６．ｈｔｍ１．

［１３］ＳＣＨＡＴＺ Ｍ Ｃ，ＴＲＡＰＮＥＬＬ Ｃ，ＤＥＬＣＨＥＲ Ａ Ｌ，ｅｔ ａ１．Ｈｉｇｈ－ｔｈｍｕ￣－

ｐｕｔ ｓｅｑｕｅｎｃｅ ａｌｉｎｍｅｎｔｇ ｕｓｉｎｇ ｇｒａｐｈｉｃｓ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔｓ［Ｊ］．ＢＭＣ

Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ，２００７，８（１）：４７４．

［１４］ＩＪＵ Ｙｏｎｇ—ｃｈａｏ，ＭＡＳＫＥＬＬ Ｄ Ｌ，ＳＣＨＭＩＤＴ Ｂ．ＣＵＤＡＳＷ＋＋：０ｐ－

ｔｉｍｉｚｉｎｇ Ｓｍｉｔｈ－Ｗａｔｅｒｍａｎ ｓｅｑｕｅｎｃｅ ｄａｔａｂａｓｅ ｓｅａｒｃｈｅｄ ｆｏｒ ＣＵＤＡ—ｅｎａ－．

ｔａｇ ａｐｐｒｏａｃｈ［Ｊ］．Ｍｏｌｅｃｕｌａｒ ａｎｄ Ｃｅｌｌｕｌａｒ Ｐｒｏｔｅｏｍｉｃｓ，２００８，７

（１２）：２４５２—２４６３．

ｂｌｅｄ ｇｒａｐｈｉｃｓ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔｓ［Ｊ］．ＢＭＣ Ｒｅｓｅａｒｃｈ Ｎｏｔｅｓ，２００９，２

（Ｊ）：７３．

［２］ＴＳＵＲ Ｄ，ＴＡＮＮＥＲ Ｓ。ＺＡＮＤＩ Ｅ，ｅｔ ａ１．Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ｏｆ ｐｏｓｔ—ｔｒａｎｓｌａ—

ｔｉｏｎａｌ ｍｏｄｉｉｆｃａｔｉｏｎｓ ｖｉａ ｂｌｉｎｄ ｓｅａｒｃｈ ｏｆ ｍａｓｓ ｓｐｅｃｔｒａ［Ｊ］．Ｎａｔｕｒｅ Ｂｉｏ—

ｔｅｃｈｎｏｌｏｇｙ，２００５，２３：１５６２－１５６７．

［１ ５］ＬＩＧＯＷＳＫＩ Ｌ，ＲＵＤＮＩＣＫＩ Ｗ．Ａｎ ｅｆｉｆｃｉｅｎｔ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｓｍｉｔｈ

ｗａｔｅｒｍａｎ ａｌｇｏｒｉｔｈｍ ｏｎ ＧＰＵ ｕｓｉｎｇ ＣＵＤＡ．ｆ０ｒ ｍａｓｓｉｖｅｌｙ ｐａｒｌｌｅｌａ ｓｃａｎ—

［３］谢靖宇，谢深泉．一种鉴定蛋白质突变和翻译后修饰的算法

［Ｊ］．计算机工程与应用，２００７，４３（２８）：６１．６４．

［４］ＦＲＡＮＫ Ａ Ｍ．Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｔａｎｄｅｍ ｍａｓｓ ｓｐｅｃｔｒｏｍｅｔｒｙ—ｂａｓｅｄ ｐｒｏ．

ｔｅｏｍｉｅｓ［Ｄ］．Ｓａｎ Ｄｉｅｇｏ：Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｃａｌｉｆｏｒｎｉａ，２００８．

［５］ＭＡＮＡＶＳＫＩ Ｓ Ａ，ＶＡＬＬＥ Ｇ．ＣＵＤＡ ｃｏｍｐａｔｉｂｌｅ ＧＰＵ ｃａｒｄｓ ａｓ ｅｆｉｆ．

ｃｉｅｎｔ ｈａｒｄｗａｒｅ ａｃｃｅｌｅｒａｔｏｒｓ ｆｏｒ Ｓｍｉｔｈ－Ｗａｔｅｒｍａｎ ｓｅｑｕｅｎｃｅ ａｌｉｇｎｍｅｎｔ

ｎｉｎｇ ｏｆ ｓｅｑｕｅｎｃｅ ｄａｔａｂａｓｅｓ［Ｃ］／／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ ｗ０ｒｋ—

ｓｈｏｐ Ｏｌｌ Ｈｉｇｈ Ｐｅｒｆｏｒｍａｎｃｅ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｂｉｏｌｏｇｙ．２００９：ｌ一８．

［１６］ＫＩＲＫ Ｄ，ＨＷＵＷｅｎ－ｍｅｉ．ＥＣＥ ４９８ＡＬ：ａｐｐｌｉｅｄ ｐａｒｌｌａｅｌ ｐｒｏｇｒａｍｍｉｎｇ

［ＥＢ／ＯＬ］．（２０１０）［２０１０—０３－１ １］．ｈｔｔｐ：／／ｃｏｕｒｓｅｓ．ｅｃｅ．ｉｌｌｉｎｏｉｓ．

ｅｄｕ／ｅｃｅ４９８／ａＬ／．

［１７］张舒，褚艳利．ＧＰＵ高性能运算之ＣＵＤＡ［Ｍ］．北京：中国水利

水电出版社，２００９：１４，４４，５８，１４３，１５２，１６６．

［Ｊ］．ＢＭＣ Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ，２００８，９（Ｓｕｐｐｌ ２）：Ｓ１０．

［６］涂强．蛋白质翻译后修饰鉴定软件ＩｎｓＰｅｃＴ的并行及优化研究

［Ｄ］．北京：中国科学院研究生院，２００９．

［７］ＮＶＩＤＩＡ Ｃｏｒｐｏｒａｔｉｏｎ．ＮＶＩＤＩＡ ＣＵＤＡ Ｐｒｏｇｒａｍｍｉｎｇ Ｇｕｉｄｅ ｖｅｒｓｉｏｎ ２．

３．１［Ｒ］．２００９．

［８］ＦＥＳＴＥＲ Ｔ，ＳＣＨＲＥＩＢＥＲ Ｆ，ＳＴＲＩＣＫＥＲＴ Ｍ．ＣＵＤＡ ｂａｓｅｄ ｍｕｌｔｉ—

ｃｏｌｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ＭＤＳ—ｂａｓｅｄ ｂｉｏｉｎｆｏｒｍａｔｉｃｓ ａｌｇｏｒｉｔｈｍｓ［Ｃ］／／

．

［１８］ＴＡＮＮＥＲ Ｓ，ＳＨＵ Ｈｏｎｇ－ｊｕｎ，ＦＲＡＮＫ Ａ，ｅｔ ａ１．Ｉｎｓｐｅｃｔ：ｆａｓｔ ａｎｄ ａｃ—

ｃｕｒａｔｅ ｉｄｅｎｔｉｉｆｃａｔｉｏｎ ｏｆ ｐｏｓｔ－ｔｒａｎｓｌａｔｉｏｎａｌｌｙ ｍｏｄｉｉｆｅｄ ｐｅｐｔｉｄｅｓ ｆｒｏｍ ｔａｎ－

ｄｅｍ ｍａｓｓ ｓｐｅｃｔｒａ［Ｊ］．Ａｎａｉｌｙｔｉｃａｌ Ｃｈｅｍｉｓｔｒｙ，２００５，７７（１４）：４６２６—

４６３９．

［１９］ＵＥＮＧ Ｓ Ｚ，ＬＡＴＨＡＲＡ Ｍ，ＢＡＧＨＳＯＲＫＨＩ Ｓ Ｓ，ｅｔ ａ１．ＣＵＤＡ—ｌｉｔｅ：ｒｅ．

ｄｕｃｉｎｇ ＧＰＵ ｐｒｏｇｒａｍｍｉｎｇ ｃｏｍｐｌｅｘｉｔｙ：ｌｎｇｕａｇｅｓａ ａｎｄ ｃｏｍｐｉｌｅｒｓ ｆｏｒ ｐａｒ－

Ｐｒｏｅ ｏｆ Ｇｅｒｍａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ．２００９：６７．７９．

ｌｌａｅｌ ｃｏｍｐｕｔｉｎｇ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ２ｈｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ．２００８：

１—１５． ，

［９］李博，刘国峰，刘洪．地震叠前时间偏移的一种图形处理器提速

实现方法［Ｊ］．地球物理学报，２００９，５２（１）：２４５．２５２．

［１０］张庆丹，戴正华，冯圣中，等．基于ＧＰＵ的串匹配算法研究［Ｊ］．

计算机应用，２００６，２６（７）：１７３５—１７３７．

［２Ｏ］邓仰东．ＮＶＩＤＩＡ ＣＵＤＡ超大规模并行程序设计训练课程：性能

提升［ＥＢ／ＯＬ］．（２００９）［２０１０・０３—１１］．ｈｔｔｐ：／／ｅｕｄａ．ｅｓｄｎ．ｎｅｔ／

Ｃｌｉｅｎｔ／ＣＵＤＡ ｌｅｃｔｕｒｅ．ｒａｒ．

（上接第３４０５页）加，系统Ｔｏｐ—ｎ查准率均不断下降，反映了结果

ｈａｖｉｏｒ：Ｇｏｏｇｌｅ ｍｏｂｉｌｅ ｓｅａｒｃｈ［ｃ］／／Ｐｒｏｃ ｏｆ ＳＩＧＣＨＩ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ

Ｈｕｍａｎ Ｆａｃｔｏｒｓ ｉｎ Ｃｏｍｐｕｔｉｎｇ Ｓｙｓｔｅｍｓ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ。２０ｏ６：

７Ｏ１．７０９．

的紧前趋势。个性化系统具有相对更高的查准率，表明本系统

相关结果排名更趋于靠前，实现了系统设计的目标。

Ｏ

［２］ＨＡＶＥＬＩＷＡＬＡ Ｔ Ｈ＿Ｔｏｐｉｃ—ｓｅｎｓｉｔｉｖｅ ｐａｇｅ ｒａｎｋ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ｌｌｔｈ

Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｅｅ ｏｎ Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ，

２００２ １５ｌ７－５２６．

得Ｏ

。

霸０

０

［３］吴晓，李丹宁，林洁．个性化搜索引擎中用户兴趣模型的研究

［ｃ］／／ｇ三届全国信息检索与内容安全学术会议论文集．２００７：

８２９—８３２．

＿标准－十性化

◆ 标准一个性化

图３平均查准率

图４ Ｔｏｐ一 查准率

［４］ＬＩＵ Ｆ，Ｙｕ Ｃ，ＭＥＮＧ Ｗｅｉ－ｙｉ．Ｐｅｒｓｏｎａｌｉｚｅｄ Ｗｅｂ ｓｅａｒｃｈ ｆｏｒ ｉｍｐｒｏｖｉｎｇ

ｒｅｔｉｒｅｖａｌ ｅｆｆｅｃｔｉｖｅｎｅｓｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎ￥ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ

Ｅｎｇｉｎｅｅｒｉｎｇ，２００４，１６（１）：２８—４０．

４结束语

由于移动用户的应用特点，对信息的精确获取和排序成为

了一个需要重点解决的问题。本文设计了一个个性化的移动

搜索模型，与其他模型相比，它有两方面的优势：更细粒度的兴

趣映射和基于反馈机制的本体概念描述。最后设计了相应的

实验，其结果表明，本文的系统在查全率和查准率上都有较大

的提升。 ‘

参考文献：

［１］ＫＡＭＶＡＲ Ｍ，ＢＡＬＵＪＡ Ｓ．Ａ ｌａｒｇｅ ｓｃａｌｅ ｓｔｕｄｙ ｏｆ ｗｉｒｅｌｅｓｓ ｓｅａｒｃｈ ｂｅ—

［５］ＶＡＲＭＡ Ｖ，ＳＲＩＨＡＲＳＨＡ Ｎ，ＰＩＮＧＡＬＩ Ｐ，ｅｔ ａ１．Ｐｅｒｓｏｎａｌｉｚｅｄ Ｗｅｂ

ｓｅａｒｃｈ ｅｎｇｉｎｅ ｆｏｒ ｍｏｂｉｌｅ ｄｅｖｉｃｅｓ［Ｃ］／／Ｐｒｏｅ ｆｏ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ

ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｉｎｆｏｒｍａｔｉｏｎ Ａｃｃｅｓｓ．２ｏｏ６．

［６］ＳＩＥＧ Ａ，ＭＯＢＡＳＨＥＲ Ｂ，ＢＵＲＫＥ Ｒ．Ｏｎｔｏｌｏｇｉｃａｌ ｕｓｅｒ ｐｒｏｆｉｌｅｓ ｆｏｒ

ｐｅｒｓｏｎａｌｉｚｅｄ Ｗｅｂ ｓｅａｒｃｈ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ５ｔｈ Ｗｏｒｋｓｈｏｐ ｏｕ Ｉｎｔｅｌｌｉ—

ｇｅｎｔ Ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ Ｗｅｂ Ｐｅｍｏｎａｌｉｚａｔｉｏｎ．２００７．

［７］ＧＡＵＣＨ Ｓ，ＣＨＡＦＦＥＥ Ｊ，ＰＲＥＴＳＣＨＮＥＲ Ａ．Ｏｎｔｏｌｏｇｙ－ｂａｓｅｄ ｐｅｒｓｏｎａ．

１ｉｚｅｄ ｓｅａｒｃｈ ａｎｄ ｂｒｏｗｓｉｎｇ［Ｊ］．Ｗｅｂ Ｉｎｔｅｌｌｉｇｅｎｃｅ ａｎｄ Ａｇｅｎｔ Ｓｙｓ－

ｔｅｒｎｓ，２ｏｏ３，１（３—４）：２１９－２３４．