Measuring the Similarity of Protein Structures Using Image Compression Algorithms

Morihiro HAYASHIDA; Tatsuya AKUTSU

doi:10.1587/transinf.E94.D.2468

Measuring the Similarity of Protein Structures Using Image Compression Algorithms

Morihiro HAYASHIDA, Tatsuya AKUTSU

Full Text Views

0

Share
Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E94-D No.12 pp.2468-2478

Publication Date: 2011/12/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E94.D.2468

Type of Manuscript: PAPER

Category: Artificial Intelligence, Data Mining

Cite this

Copy

Morihiro HAYASHIDA, Tatsuya AKUTSU, "Measuring the Similarity of Protein Structures Using Image Compression Algorithms" in IEICE TRANSACTIONS on Information, vol. E94-D, no. 12, pp. 2468-2478, December 2011, doi: 10.1587/transinf.E94.D.2468.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.E94.D.2468/_p

Copy

@ARTICLE{e94-d_12_2468,
author={Morihiro HAYASHIDA, Tatsuya AKUTSU, },
journal={IEICE TRANSACTIONS on Information},
title={Measuring the Similarity of Protein Structures Using Image Compression Algorithms},
year={2011},
volume={E94-D},
number={12},
pages={2468-2478},
abstract={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.},
keywords={},
doi={10.1587/transinf.E94.D.2468},
ISSN={1745-1361},
month={December},}

Copy

TY - JOUR
TI - Measuring the Similarity of Protein Structures Using Image Compression Algorithms
T2 - IEICE TRANSACTIONS on Information
SP - 2468
EP - 2478
AU - Morihiro HAYASHIDA
AU - Tatsuya AKUTSU
PY - 2011
DO - 10.1587/transinf.E94.D.2468
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E94-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2011
AB - 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.
ER -