The Universal Similarity Metric, Applied to Contact Maps Comparison in A Two-Dimensional Space

Comparing protein structures based on their contact maps is an important problem in structural proteomics. Building a system for reconstructing protein tertiary struc-tures from their contact maps is one of the motivations for devising novel contact map comparison algorithms. Several methods that address the contact map compar-ison problem have been designed which are briefly discussed in this thesis. However, they suggest scoring schemes that do not satisfy the two characteristics of “metricity” and “universality”. In this research we investigate the applicability of the Universal Similarity Metric (USM) to the contact map comparison problem. The USM is an information theoretical measure which is based on the concept of Kolmogorov com-plexity. The ultimate goal of this research is to use the USM in case-based reasoning system to predict protein structures from their predicted contact maps. The fact that the contact maps that will be used in such a system are the ones which are predicted from the protein sequences and are not noise-free, implies that we should investigate the noise-sensitivity of the USM. This is the first attempt to study th