SGFSC: speeding the gene functional similarity calculation based on hash tables

BMC Bioinformatics

Methodology Article

Zhen Tian¹  Chunyu Wang¹  Xiaoyan Liu¹  Maozu Guo¹  Zhixia Teng² 

[1] School of Computer Science and Technology, Harbin Institute of Technology, 150001, Harbin, People’s Republic of China;School of Computer Science and Technology, Harbin Institute of Technology, 150001, Harbin, People’s Republic of China;Department of Information Management and Information System, Northeast Forestry University, 150001, Harbin, People’s Republic of China;

关键词: Gene ontology;    Hash table;    Gene functional similarity;   

DOI  :  10.1186/s12859-016-1294-0

 received in 2016-05-04, accepted in 2016-10-19,  发布年份 2016

来源: Springer

【 摘 要 】

BackgroundIn recent years, many measures of gene functional similarity have been proposed and widely used in all kinds of essential research. These methods are mainly divided into two categories: pairwise approaches and group-wise approaches. However, a common problem with these methods is their time consumption, especially when measuring the gene functional similarities of a large number of gene pairs. The problem of computational efficiency for pairwise approaches is even more prominent because they are dependent on the combination of semantic similarity. Therefore, the efficient measurement of gene functional similarity remains a challenging problem.ResultsTo speed current gene functional similarity calculation methods, a novel two-step computing strategy is proposed: (1) establish a hash table for each method to store essential information obtained from the Gene Ontology (GO) graph and (2) measure gene functional similarity based on the corresponding hash table. There is no need to traverse the GO graph repeatedly for each method with the help of the hash table. The analysis of time complexity shows that the computational efficiency of these methods is significantly improved. We also implement a novel Speeding Gene Functional Similarity Calculation tool, namely SGFSC, which is bundled with seven typical measures using our proposed strategy. Further experiments show the great advantage of SGFSC in measuring gene functional similarity on the whole genomic scale.ConclusionsThe proposed strategy is successful in speeding current gene functional similarity calculation methods. SGFSC is an efficient tool that is freely available at http://nclab.hit.edu.cn/SGFSC. The source code of SGFSC can be downloaded from http://pan.baidu.com/s/1dFFmvpZ.

【 授权许可】

CC BY   
© The Author(s). 2016

【 图 表 】

12864_2017_3777_Article_IEq7.gif

12864_2017_4271_Article_IEq2.gif

12864_2017_3733_Article_IEq47.gif