{'fraction_non_alphanumeric': 0.03242646320650537, 'fraction_numerical': 0.017568517217146872, 'mean_word_length': 4.516057585825028, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Applications of cuckoo search and ant lion optimization for analyzing protein-protein interaction through regularized Markov clustering on coronavirus

All living viruses have important structures such as protein. Proteins can interact with each other forming large networks of Protein-Protein Interaction (PPI). In order to facilitate the study of these PPI networks, there needs to be clustering analysis of the PPI. In this research, we use PPI network datasets from SARS-CoV-2 and humans. The interactions of the PPI network will then be formed into graphs. Regularized Markov Clustering (RMCL) is used to perform graph clustering. RMCL consists of three main steps which are regularization, inflation, and pruning. The RMCL algorithm is a variant of Markov Clustering (MCL). However, the inflation parameter in RMCL must be inputted manually by the user to obtain the best results. To solve the limitations of RMCL, we developed a new method by combining each Cuckoo Search (CS) and Ant Lion Optimization (ALO) with the original RMCL algorithm. The optimizers are used to optimize the inflation parameter in RMCL. CS and ALO are a part of swarm intelligence which is inspired by the behaviour of cuckoo birds and antlions in nature. The results show that the interactions formed from CS-RMCL vary from 1401 to 1402. It is more stable than the interactions formed from ALO-RMCL which ranges from 1408 to 3641. The difference between the best elite in each iteration of ALO-RMCL is very influential to the interaction compared to the best nest from the CS-RMCL.


Introduction
SARS-Cov-2 is a novel type of Coronavirus that has spread globally and is closely related to the SARS-CoV virus which previously described and identified in the 2002-2003 outbreak [1]. SARS-CoV-2 caused worldwide pandemic with the disease named COVID-19. The structure of SARS-CoV-2 is similar with other viruses which contains capsids in their body. The capsids of viruses consist of protein that is used as a protective coat which makes up an important structure of the virus [2].
A recent study found that a human protein named Angiotensin Converting Enzyme 2 (ACE2) is responsible as a host receptor for human-to-human transmission of COVID-19 because it can strongly bind to SARS-CoV-2 [3]. One of the application of bioinformatics is Protein-Protein Interaction (PPI) network. The interactions of each protein form very large networks of PPI and can be represented in a graph. A big number of large clusters and singleton clusters formed by the process of clustering is a problem occurred in clustering [4]. Therefore, clustering analysis is needed to form a better representation of protein interactions [5].
The MCL algorithm is used as clustering method in many scientific disciplines to solve general problem of graph clustering, including the applications of bioinformatics [6]. Satuluri [7]. RMCL also has its limitations which is that the inflation parameter must be inputted manually by the researcher. RMCL can be optimized with optimization algorithms which can automatically find the appropriate inflation parameter.
Yang and Deb developed Cuckoo Search (CS) algorithm in 2009 [8]. The parasitic behavior of cuckoo birds during breeding inspired them to develop the CS algorithm that is adapted from Swarm Intelligence [9]. Apart from cuckoo birds, antlions also inspired an optimization algorithm named Ant Lion Optimization (ALO) developed by Mirjalili in 2015 [10]. The ALO algorithm adapts the hunting behaviour of antlion's larvae and was used in solving many applications. To resolve the weakness of RMCL, we used the CS and ALO algorithms to optimize the inflation parameter in RMCL.

Basic Theory of Graph
Out of the many topics in mathematics, graph theory is one that can simplify a problem as a network. Graph theory is also used in other scientific disciplines, such as solving many problems in computer science. A graph = ( , ) consist of a nonempty set = ( 1 , 2 , … ) called vertices (or nodes) and a nonempty set = ( 1 , 2 , … ) called edges where each edge has either one or two vertices associated with edge [11].
If the endpoint of an edge in the undirected graph on graph are two vertices and , then and are called adjacent to graph [11]. A symmetric matrix = [ ] of is the adjacency matrix of graph where the entries of shows the edge connection between two vertices. The connection between each vertice on matrix is arranged as follows:

Basic Theory of Overlapping Clustering
One of the clustering techniques that allow the elements in it to be part of several clusters is called overlapping clustering. Overlapping clustering is better to use on modelling relationship between the element beside partitional clustering [4]. Partitional clustering is clustering technique where data is parted as group without overlap. In biological science, clustering technique is many used to identify functional module network on gene expression data by grouping gene which has same expression to entry at the same group [12].

Regularized Markov Clustering
Generally, the clustering result of the MCL algorithm produces too many clustering outputs because the MCL algorithm "overfits" the graph [7]. This occurs because there is no penalty when the neighboring nodes' columns vary extensively [4]. The RMCL algorithm was made to overcome the "overfitting" problem of MCL. The problem of output fragmentation is solved in RMCL by regularizing or smoothing the flow distribution out of the nodes concerning its neighboring nodes [7]. An operator is changed in the RMCL algorithm that is its expansion operator. The regularization operator in RMCL is is the canonical transition matrix. All of the steps in RMCL except the regularization step are same with the MCL algorithm [7]. The pseudo-code for the RMCL algorithm modified by Ginanjar [4] is given in Table 1.

CS-RMCL
Yang and Deb developed the CS algorithm as an optimization algorithm in 2009 [8]. Cuckoo birds inspired Yang and Deb to create the CS algorithm as part of Swarm Intelligence. Cuckoo birds lay their eggs in other birds' nest and not in their own which makes them parasitic during their breeding. The adaptability of cuckoo eggs helps last in the foreign nest and keep it from being destroyed by the nest owner because the eggs can change their shape to be similar with the nest owner's egg. If the cuckoo birds' eggs hatch after the nest owner eggs do, then the cuckoo birds will spend their food and cause the nest owner's birds to die [13]. If the cuckoo birds' eggs hatch before the nest owner's eggs do, then the cuckoo birds will drop the eggs from the nest [2]. The CS algorithm will find the best nest to optimize the inflation parameter in the RMCL algorithm so that we named this algorithm with CS-RMCL algorithm. Cuckoo birds' behavior to search the best nest will be used to find the inflation parameter automatically. The pseudo-code for the CS-RMCL algorithm adapted from Vira [2] is given in Table 2.

ALO-RMCL
Marijalili developed the ALO algorithm as an optimization algorithm in 2015 [10]. The ALO algorithm was inspired by antlion's larvae behaviour when it forages in nature. Antlions have two main phases in their lifecycle, the larvae phase and adult phase. Antlions hunt to forage in their larvae period and reproduce in adult period. The antlion's larvae digs conical holes in the sand. They move around a circular path and dump the sand with their large jaws [14]. The ALO algorithm will find the best elite to optimize the inflation parameter in the RMCL algorithm so that we named this algorithm with ALO-RMCL algorithm. Antlions' behavior to find the best elite in nature will automatically find the inflation parameter. The pseudo-code for the ALO-RMCL algorithm is given in Table 3.

Input:
Adjacency Matrix of graph Step 1: Add self-loop to the graph, = + 1 Step 2: Create Markov matrix and by normalizing each column of matrix , which is = = −1 with is diagonal degree matrix of Step 3: • Initialize the clusters as ants and position of antlions • Calculate the fitness of ants and antlions • Find the best antlion and assume it as the elite (determine optimum) Step 4: Repeat step 5 until step 6 Step 5: (  Step 7: Repeat step 8 until step 10 Step 8: = ( ) ∶= * Step 9: = ( , ) Step 10: = ( ) = 0 if < Until Global Chaos of matrix < ℎ ℎ

Result and Discussion
This study uses data on the PPI network of SARS-CoV-2 extracted from the online database BioGRID version 3.5.187. There are 1184 proteins and 1437 interactions of SARS-CoV-2 and human protein as shown in Figure 1. Each protein is represented as a node. The purple nodes are human proteins and the yellow nodes are SARS-CoV-2 proteins. The lines connecting each protein represent the interactions between the SARS-CoV-2 and human proteins. Proteins which their interactions form like a flower show that proteins in it have a strong relation. The farther the connections from the proteins are formed, the weaker the interactions are.

Figure 1. PPI Networks on SARS-CoV-2 and Human
The simulation of CS-RMCL and ALO-RMCL is performed in RStudio version 1.3.1073 by using the R programming language. This simulation program is run on a computer with the following specifications: Intel (R) Core (TM) i7-6700 CPU @ 3.40GHz (8 CPUs), ~3.4GHz; 24 GB RAM and Windows 7 Professional 64-bit operating system. This simulation uses an inflation parameter that is automatically found from CS and ALO with iterations as many as 100, 500, 1000, and 10000. The different iterations are used to figure out the alterations of the cluster and interactions formed by each iteration from CS-RMCL and ALO-RMCL. In this research, the clustering results from CS-RMCL and ALO-RMCL is 11 clusters in all trials. The different result is significantly shown by the interaction formed on each inflation parameter and iteration.
The results of CS-RMCL simulation with = 9.785 of inflation and = 100 is shown in Figure 2.