Measuring the Similarity of Protein Structures Using Image Compression Algorithms
Measuring the Similarity of Protein Structures Using Image Compression Algorithms
复制标题
DOI：
10.1587/transinf.e94.d.2468
复制
发表时间：
2011-12
期刊：
影响因子：
--
通讯作者：
M. Hayashida;T. Akutsu
中科院分区：
文献类型：
--
作者：
M. Hayashida;T. Akutsu
为了测量生物序列和结构（如DNA序列、蛋白质序列和三级结构）的相似性，已经开发了几种基于压缩的方法。然而，它们仅基于顺序数据的压缩算法。例如，蛋白质结构可以用二维距离矩阵表示。因此，由于图像压缩算法水平和垂直压缩数据，因此期望图像压缩对测量蛋白质结构的相似性有用。本文提出了一系列测量蛋白质结构相似性的方法。在该方法中，将原始蛋白质结构转换为距离矩阵，将其视为二维图像。然后，通过对拼接图像的一种压缩比来衡量两个蛋白质结构的相似性。我们采用了几种图像压缩算法，JPEG、GIF、PNG、IFS和SPC。由于SPC算法在其他图像压缩方法中往往能获得较好的压缩效果，并且SPC算法简单，易于修改，因此我们对SPC算法进行了改进，得到了MSPC算法。我们将提出的方法应用于蛋白质结构的聚类，并进行受试者工作特征（ROC）分析。计算实验结果表明，在现有的基于压缩的方法中，MSPC的性能是最好的。我们还对基于图像压缩的蛋白质结构比较的时间复杂度和Kolmogorov复杂度给出了一些理论结果。
For measuring the similarity of biological sequences and structures such as DNA sequences, protein sequences, and tertiary structures, several compression-based methods have been developed. However, they are based on compression algorithms only for sequential data. For instance, protein structures can be represented by two-dimensional distance matrices. Therefore, it is expected that image compression is useful for measuring the similarity of protein structures because image compression algorithms compress data horizontally and vertically. This paper proposes series of methods for measuring the similarity of protein structures. In the methods, an original protein structure is transformed into a distance matrix, which is regarded as a two-dimensional image. Then, the similarity of two protein structures is measured by a kind of compression ratio of the concatenated image. We employed several image compression algorithms, JPEG, GIF, PNG, IFS, and SPC. Since SPC often gave better results among the other image compression methods, and it is simple and easy to be modified, we modified SPC and obtained MSPC. We applied the proposed methods to clustering of protein structures, and performed Receiver Operating Characteristic (ROC) analysis. The results of computational experiments suggest that MSPC has the best performance among existing compression-based methods. We also present some theoretical results on the time complexity and Kolmogorov complexity of image compression-based protein structure comparison.