Initial protein structural comparisons were sequence-based. Since amino acids that are distant in the sequence can be close in the 3-dimensional (3D) structure, 3D contact approaches can complement sequence approaches. Traditional 3D contact approaches study 3D structures directly and are alignment-based. Instead, 3D structures can be modeled as protein structure networks (PSNs). Then, network approaches can compare proteins by comparing their PSNs. These can be alignment-based or alignment-free. We focus on the latter. Existing network alignment-free approaches have drawbacks: 1) They rely on naive measures of network topology. 2) They are not robust to PSN size. They cannot integrate 3) multiple PSN measures or 4) PSN data with sequence data, although this could improve comparison because the different data types capture complementary aspects of the protein structure. We address this by: 1) exploiting well-established graphlet measures via a new network alignment-free approach, 2) introducing normalized graphlet measures to remove the bias of PSN size, 3) allowing for integrating multiple PSN measures, and 4) using ordered graphlets to combine the complementary PSN data and sequence (specifically, residue order) data. We compare synthetic networks and real-world PSNs more accurately and faster than existing network (alignment-free and alignment-based), 3D contact, or sequence approaches. Motivation and related work. Proteins perform important cellular functions. While understanding protein function is clearly important, doing so experimentally is expensive and time-consuming 1,2 . Because of this, the functions of many proteins remain unknown 2,3 . Consequently, computational prediction of protein function has received attention. In this context, protein structural comparison (PC) aims to quantify similarity between proteins with respect to their sequence or 3-dimensional (3D) structural patterns. Then, functions of unannotated proteins can be predicted based on functions of similar, annotated proteins. By "function", we mean traditional notions of protein function, such as its biological process, molecular function, or cellular localization 4 , or any protein characteristic (e.g., length, hydrophobicity/hydrophilicity, or folding rate), as long as the given characteristic is expected to correlate well with the protein structure. In this study, we propose a new PC approach, which we evaluate in an established way: by measuring how accurately it captures expected (dis)similarities between known groups of structurally (dis)similar proteins 5 , such as protein structural classes from Class, Architecture, Topology, Homology (CATH) 6,7 , or Structural Classification of Proteins (SCOP) 8 . Application of our proposed PC approach to protein function prediction is out of the scope of the current study and is the subject of future work. Early PC has relied on sequence analyses 9-11 . Due to advancements of high-throughput sequencing technologies, rich sequence data are available for many species, and thus, comprehensive sequence pattern searches are possible. However, amino acids that are distant in the linear sequence can be close in 3D structure. Thus, 3D structural analyses can reveal patterns that might not be apparent from the sequence alone 12 . For example, while high sequence similarity between proteins typically indicates their high structural and functional similarity 3 , proteins with low sequence similarity can still be structurally similar and perform similar function 13, 14 . In this case, 3D structural approaches, unlike sequence approaches, can correctly identify structurally and thus functionally similar proteins. On the other extreme, proteins with high sequence similarity can be structurally dissimilar and perform different functions [15] [16] [17] [18] [19] . In this case, 3D structural approaches, unlike sequence approaches, can correctly identify structurally and thus functionally different proteins. 3D structural approaches can be categorized into traditional 3D contact approaches, which are alignment-based, and network approaches, which can be alignment-based or alignment-free. By alignment-based (3D contact or network) approaches, we mean approaches whose main goal is to map amino acid residues between the compared proteins in a way that conserves the maximum amount of common substructure. In the process, alignment-based approaches can and typically do quantify similarity between the compared protein structures, and they do so under their resulting residue mappings. Given this, alignment-based approaches can and have been used in the task of PC as we define it 5,20 , even though they are not necessarily directly designed for this task. On the other hand, by alignment-free (network) approaches, we mean approaches whose main goal is to quantify similarity between the compared protein structures independent of any residue mapping, typically by extracting from each structure some network patterns (also called network properties, network features, network fingerprints, or measures of network topology) and comparing the patterns between the structures. Alignment-free approaches are directly designed for the task of PC as we define it. We note that there exist approaches that are alignment-free but not network-based 21 , which are out of the scope of our study. Below, we discuss 3D contact alignment-based PC approaches, followed by network alignment-based PC approaches, followed by network alignment-free PC approaches. 3D contact alignment-based PC approaches are typically rigid-body approaches 22,23 , meaning that they treat proteins as rigid objects. Such approaches aim to identify alignments that satisfy two objectives: 1) they maximize the number of mapped residues and 2) they minimize deviations between the mapped structures (with respect to e.g., Root Mean Square Deviation). Different rigid-body approaches mainly differ in how they combine these two objectives. There exist many approaches of this type 5,24-26 . Prominent ones are DaliLite 27 and TM-align 28 . These two approaches have explicitly been used and evaluated in the task of PC as we define it 5,20 , and are thus directly relevant for our study. Network alignment-based PC approaches are typically flexible alignment methods, meaning that they treat proteins as flexible (rather than rigid) objects, because proteins can undergo large conformational changes. These approaches align local protein regions in a rigid-body manner but account for flexibility by allowing for twists between the locally aligned regions 5,29 . Also, these approaches are typically of the Contact Map Overlap (CMO) type. That is, first, they represent a 3D protein structure consisting of n residues as a contact map, i.e., n × n matrix C, where position C ij has a value of l if residues i and j are close enough and are thus in contact, and it has a value of 0 otherwise. Note that contact maps are equivalent to protein structure networks (PSNs), in which nodes are residues and edges link spatially close amino acids 30 . Second, CMO approaches aim to compare contact maps of two proteins, in order to align a subset of residues in one protein to a subset of residues in another protein in a way that maximizes the number of common contacts and also conserves the order of the aligned residues 31 . Prominent CMO approaches are Apurva, MSVNS, AlEigen7, and GR-Align 5 . When evaluated in the task of PC as we define it, i.e., when used to compare proteins labeled with structural classes of CATH or SCOP, GR-Align outperformed Apurva, MSVNS, and AlEigen7 in terms of both accuracy and running time 5 . So, we consider GR-Align to be the state-of-the-art CMO (i.e., network alignment-based) approach. In addition to these network alignment-based approaches, GR-Align was evaluated in the same manner against the existing 3D contact alignment-based approaches (DaliLite and TM-Align mentioned above, as well as three additional approaches, MATT, Yakusa, and FAST) 5 . In terms of running time, GR-Align was the fastest. In terms of accuracy, GR-Align was superior to MATT, Yakusa, and FAST, but it was inferior or comparable to DaliLite and TM-Align. So, while GR-Align remains the state-of-the-art network alignment-based PC approach, DaliLite and TM-Align remain state-of-the-art 3D contact alignment-based PC approaches, and we continue to consider all three in our study. Network alignment-free approaches also deal with PSN representations of compared proteins, but they aim to quantify protein similarity without accounting for any residue mapping. We propose a novel network alignment-free PC approach (see below). We first compare our approach to its most direct competitors, i.e., existing alignment-free approaches. Then, we compare our approach to existing alignment-based approaches. We recognize that evaluation of alignment-free against alignment-based approaches should be taken with caution 32,33 , (because the two comparison types quantify protein similarity differently -see above). Yet, as we show later in our evaluation, existing alignment-based PC approaches are superior to existing alignment-free PC approaches and are thus our strongest (though not necessarily fairest) competitors. Next, we discuss existing network alignment-free PC approaches. Such approaches have already been developed 14,34 , to compare network topological patterns within a protein or across proteins, for example to study differences in network properties between transmembrane and globular proteins, analyze the packing topology
A popular baseline sequence feature is the amino acid composition (AAComposition), which measures the relative composition of the different amino acid types in a protein sequence REF .
GRAFENE: Graphlet-based alignment-free network approach integrates 3D structural and sequence (residue order) data to improve protein structural comparison
Scientific Reports
Scientific Reports
Computer Science Medicine Biology