利用二级质谱自动进行聚糖结构解析的从头开始算法

关于不借助数据库,根据质谱自动地从头开始解析聚糖结构（包括单糖组成、排列信息和单糖之间的连接信息）已有多年研究,然而,如何快速准确地得到结果仍然面临诸多挑战。为了降低时间复杂度,现有的方法要么采用贪心法或者启发式算法,这些算法本身就是不精确的,难以保证得到结果的准确性;要么采用剪枝法或者动态规划之类的精确算法,但是这类算法不仅时间复杂度较高,而且其中大量使用的假设和理想化模型忽视了许多对结果有影响的实验细节。诸如打分函数中对不同候选结构重复使用相同谱峰进行评分的问题,先前的精确算法常常选择回避和无视,这些被忽视的细节最终导致结果的不准确。本工作提出了基于迭代增长的方法“自底向上”地利用谱图解析聚糖结构的算法。与以往迭代方法不同,该算法中增长的单位不再是单糖,而是在算法中产生的子结构,这使得算法的运行速度大大加快。在将各种实验细节纳入算法流程的基础上,通过对20种聚糖的二级质谱图解析以及与先前算法的比较,证实了该算法具有较高的准确性（75%聚糖的正确结构被算法解析为第一）。