基于数字签名与Trie的保序子矩阵约束查询

来源：软件学报杂志2017年第8期北京时间：

作者：姜涛,李战怀,尚学群,陈伯林,李卫榜,殷知磊

单位：姜涛，西北工业大学 计算机学院, 陕西 西安 71007211,李战怀，西北工业大学 计算机学院, 陕西 西安 71007202,尚学群，西北工业大学 计算机学院, 陕西 西安 71007203,陈伯林，西北工业大学 计算机学院, 陕西 西安 71007204,李卫榜，西北工业大学 计算机学院, 陕西 西安 71007205,殷知磊，西北工业大学 计算机学院, 陕西 西安 71007206

摘要：目前，基因芯片技术飞速发展，促使生物学家积累了大量的不同实验条件下的基因表达数据.事实证明，基因芯片数据分析在理解基因功能、基因调控和分子生命过程中发挥着重要作用.保序子矩阵（order-preserving submatrix，简称OPSM）是基因芯片数据分析技术中的一种有效模型，其可以发现在部分基因和不同实验条件下具有相同表达趋势的聚类.在分析基因表达机理的过程中，OPSM的检索无疑节省了生物学家的时间与精力.目前，OPSM的查询主要是基于关键词的检索方法，但是分析者对结果具有微弱的控制力.通常，分析者所能决定的临时的参数设置往往偏离其领域知识，致使检索结果与真实想要的结果相去甚远.为了解决上述问题，提出两类基于数字签名与Trie的OPSM索引与约束查询方法.在真实数据上进行了大量的实验，实验结果表明，所提出的方法具有良好的有效性与可扩展性.

关键词：基因表达数据;OPSM(order-preserving submatrix);约束查询;数字签名;Trie;枚举序列

基金资助：国家重点基础研究发展计划（973）（2012CB316203）；国家自然科学基金（61033007，61272121，61332014，61572367，61472321，61502390）；国家高技术研究发展计划（863）（2015AA015307）；中央高校基本科研业务费专项资金（3102015JSJ0011）；西北工业大学研究生创业种子基金（Z2012128）