Due to increasing number of viral diseases (including Covid-19) rapid research with the purpose of their detection, prevention, and treatment is crucial. This article considers a problem of finding two optimal antibodies to any virus that is important for detection of disease and development of tests but not for creation of vaccine. It is worth noting that the target protein (nucleoprotein), described in this article, is the only generally established target for SARSCoV-2 diagnostics, using antigen rapid tests or any other antigen detection tools. Possible ways of solving the aforementioned problem were described using hierarchical clustering algorithm with different linkage methods. Affirmative results of dividing antibodies into groups were achieved. Hierarchical clustering, SARS-CoV-2, antibodies, viruses IDDM-2022: 5th International Conference on Informatics & Data-Driven Medicine, November 18-20, 2022, Lyon, France; ORCID: 0000-0003-1247-7511 (OZ); 0000-0001-5401-1731 (VH); 0000-0003-4250-4322 (YuL); 0000-0003-4834-9597 (YaP).
The Covid-19 epidemic has shown that it is still quite difficult for humanity to control and fight acute respiratory viral infections. According to WHO, almost 613 million people worldwide have been infected with COVID-19 and more than 6.5 million people have died due to the disease [3]. However, this is not the first and probably not the last such pandemic.
Therefore, it is crucial to conduct research as quickly as possible, so that the diseases could be easily detected and treated. The next step is the development of vaccines, as well as tests that show the number of antibodies to a particular virus. It is clear that rapid detection of the disease helps to isolate spreading of the virus and treat a patient more effectively, and vaccination improves immunity to a particular virus and reduces the likelihood of negative or even fatal consequences.
Nowadays, computers are a very powerful tool that allows solving not only mathematical problems, but also biological, chemical, and medical ones. Different types of models and algorithms including machine learning algorithms are used for this purpose. Moreover, the usage of computers helps scientists to reduce the number of experiments and routine work in laboratories around the world.
The purpose of this work is to consider the problem of finding two optimal antibodies to any virus (for example, the SARS-CoV-2) and propose possible ways to solve it using machine learning algorithms, more precisely agglomerative clustering algorithms.
There is a molecule of the SARS-CoV-2 and a set of antibodies, which consists of 43 elements. The task is to attach only two antibodies to the given virus molecule. In this article, the target molecule is
2022 Copyright for this paper by its authors. the molecule of protein (nucleoprotein). This protein is the only generally established target for COVID19 diagnostics (not the vaccine) used by practically all antigen rapid tests [10] and other antigen detection tools globally. Only two antibodies are required to form a "sandwich", which is a standard way of the determination of any protein substance. The antibodies can be either different or the same (to distinguish them, one of them is marked with "*").
For simplicity, we will assume that the experiment happens in 2D, not 3D. Antibodies are two circles of approximately the same size with a small "beak" for interaction with the virus. Antibodies attach to the virus molecule, which is represented as a smaller circle. A schematic representation of this process can be seen in Figure 1.
In the case of the considered problem, the molar weight of the target protein molecule is 45 kDa and the molar weight of the antibodies is 180 kDa. Since there is a need to attach two antibodies to a virus molecule, the main task is to find two antibodies (they can be identical) that are located at an optimal distance from each other. This means that they cannot overlap or locate too close to each other otherwise they start to compete and one of them cannot be attached.
It was discovered that this problem mostly can be solved by dividing the list of antibodies into groups according to how much they interfere with each other, or in other words, whether they can attach to the virus in the same region. If two antibodies belong to different groups, there is a very high probability that they will bind in different areas and interact better than if they were from the same group. However, in some cases, antibodies still will not be able to attach to the virus molecule.
The data considered in this paper are obtained from the experiment performed by Xema OY, Lappeenranta, Finland which consisted of several parts: 1. Conjugation of HRP to monoclonal antibodies
One of the most popular methods of conjugation HRP (Faizyme, SAR) to antibodies was used. Periodate oxidized HRP formed a covalent linkage with mAbs after the reduction of the Schiff base by sodium borohydride [9]. 2. Direct binding of mAbs to N-Ag variants
N-Ag preparations were diluted to 0,1 ug/ml by carbonate buffer pH 9,5. One hundred microliters of the solution were placed into the wells of high adsorption capacity polystyrene microplate (KHB, China) and incubated overnight at +4 °C. After removing the microwell content by vacuum, the microwells were washed once by ELISA [8] washing solution - 0,1% Tween 20 (Serva, Germany) in 0,9% sodium chloride (Merck, Germany) and filled with ELISA blocking solution (0,1M phosphate buffer containing 0.9% NaCl and 0,5% hydrolyzed casein) for 2 hours at ambient temperature, and then dried at ambient temperature for 48 hours.
The mAbs were diluted by ELISA buffer (0,1M phosphate buffer containing 0,9% NaCl and 0,1% hydrolyzed casein) at a uniform concentration of 1 ug/ml. One hundred ul of mAb solution was incubated in the wells for 30 minutes at 37 °C. The wells were washed thrice with ELISA washing solution, and HRP-conjugated sheep anti-mouse Ig-HRP conjugate (Cat# AS302-HRP, Xema) in working dilution was added to the wells for another 30 minutes at 37 °C. After 5 washing with ELISA washing solution, the TMB chromogenic substrate (Cat#R055, Xema) was added into the wells for 15 minutes, the reaction was stopped by the addition of 5% sulfuric acid and optical density at 450 nm (OD450) was measured on HiPo microplate reader (Biosan, Latvia) 3. Cross-inhibition of mAbs by direct binding to solid phase N-Ag.
Full-length N-Ag was coated onto the surface of polystyrene wells at 0,5 ug/ml (see the previous paragraph). In the preliminary test, each HRP-conjugated mAb was serially diluted (10x) in the microwells from 1:100 to 1:1 million and incubated for 30 minutes at 37 °C. Then the reaction was finalized by washing, TMB substrate, and stop solution as described in the previous paragraph. The dilution factor of each conjugate giving the OD450 within the range 1,0-1,5 was used as working dilution for the main cross-inhibition experiment as follows.
Fifty microliters of the working dilution of each HRP-conjugated mAb were added into the antigencoated microwells concurrently with the equal volume of ELISA buffer (reference wells) or all mAbs diluted to 10 ug/ml in the same buffer. After 30 minutes of incubation at 37 °C, the reaction was finalized as described above. All the combinations were run in duplicates. The data for each combination of HRP labeled and unlabeled mAbs are shown as the inhibition percentage: (average OD450 of actual combination – average OD450 of reference wells)/average OD450 of reference wells.
Data are presented in the form of a table with 43 rows that represent antibodies and 32 columns that represent marked antibodies, where each cell is the cross-inhibition index of the marked antibody and unmarked. In the row labeled as "blank", the maximum values of the cross-inhibition index for the corresponding marked antibody are given. The value in each cell ranges from zero to the value in the "blank" cell of the corresponding column. An example of data is shown in Figure 2.
Eventually, the problem, described in this article, is the dataset elements grouping problem, which is considered to be a problem of clustering. That is why it was decided to apply one of the most popular types of clustering – the hierarchical algorithms, namely its agglomerative subspecies. There were chosen several linkage methods [1]: • • • •
Ward linkage – the increase in variance for the cluster being merged Complete linkage – the maximum distance between elements of each cluster Average linkage – the mean distance between elements of each cluster
Single linkage – the minimum distance between elements of each cluster
In addition, it was decided to use the simplest Euclidean distance (
( , ) = √∑( − )2, , = −(
), ,
Before applying any algorithm, equation (
The new values represent the percentage ratio between the value in the cell and the maximum value for the corresponding column. The new values are in the range of 0 to 1.
To develop an application for solving the described problem, the Python programming language was used. In particular, the “pandas” library was used to work with data and the “scikit-learn” library was used for clustering [4, 7].
The threshold was selected using the Elbow method based on the vector of distances between clusters [5, 6].
The expected results are shown in Table 1. Based on it we aim to obtain 11 groups (or 7 large groups) with different numbers of antibodies in each of them. From the experiment, it is known that the best interaction will be between antibodies from the group 3B (X155, X41, X213, X32) and 4A (NP3706) or 4B (X211).
As a result, 4 different outputs for each linkage method were received. The dendrogram in Figure 3 shows results for the usage of Ward linkage with a distance threshold equal to 1.5.
As a result of this algorithm, 7 clusters were identified. Table 2 shows the result of clustering where each column contains a list of antibodies that belong to the corresponding cluster.
From the result, it is obvious that cluster number 1 matches group 3B, cluster 5 completely matches group 2B/3, and cluster 7 matches group 1A (they are marked in green). Also, cluster 3 combines groups 1B, and 2, and cluster 4 corresponds to group 3A without the element NP1527, which is in cluster 6, which also contains groups 4A and 4B (they are marked in yellow and orange).
The dendrogram in Figure 4 shows the results of the usage of complete linkage with a distance threshold equal to 1.2.
As a result of this algorithm, 9 clusters were identified. Table 3 shows the result of clustering. As shown, cluster number 4 matches group 1A and cluster 8 completely matches group 2B/3 (they are marked in green). Also, cluster 2 combines groups 1B and 2, cluster 5 corresponds to group 3A without the element NP1527, which is in cluster 3, which also contains groups 4A and 4B, in addition, cluster 6 and cluster 9 contain the elements from group 3B (they are marked in yellow and orange). Table 3 Result for agglomerative clustering with complete linkage 1
2
The dendrogram in Figure 5 shows the results of the usage of average linkage with a distance threshold equal to 0.97.
As a result of this algorithm, 11 clusters were identified. Table 4 shows the result of clustering. As shown, cluster number 2 matches group 3B, cluster 5 completely matches group 1A, and cluster 8 matches group 2B/3 (they are marked in green). Also, cluster 6 combines groups 1B, and 2, and clusters 9, 10, and 11 correspond to group 3A without the element NP1527, which is in cluster 6, which also contains groups 4A and 4B (they are marked in yellow and orange).
The dendrogram in Figure 6 shows the results of the usage of a single linkage with a distance threshold equal to 0.75.
As a result of this algorithm, 13 clusters were identified. Table 5 shows the result of clustering. As shown, cluster number 2 matches group 3B, cluster 3 completely matches group 1A and cluster 6 matches group 1A, and cluster 13 matches group 4B (they are marked in green). Also, cluster 4 combines groups 1B, and 2, and cluster 6 and 11 contains items from group 5 (they are marked in yellow and orange).
As a metric of accuracy, the total amount of elements in the clusters, which fully correspond to the expected result, was taken. Based on this metric, it is obvious that the algorithm, which used a single linkage method, gives the best result. However, the algorithms that used ward linkage and average linkage methods are not much worse. Surprisingly, the algorithm, which used the complete linkage method is the worst.
Even though the amount of data may seem to be small (40x30 matrix), the developed application does the amount of work in a short time (1-2 minutes), that would take a person several days to complete. Moreover, as the sample data size increases, the amount of time it takes for the computer to execute the algorithm will remain small compared to the time it would take a person to perform the same task.
In conclusion, hierarchical clustering methods have shown themselves to be quite suitable for a given problem. However, they do not take into account the order in which it forms the clusters yet (the order of the clusters is not the same as the order of the groups in the expected result), but it is also a key aspect of this problem.
[5] Kneed documentation, Parameter Example, 2020, URL: https://kneed.readthedocs.io/ en/stable/parameters.html [6] I. D. Baruah, Cheat sheet for implementing 7 methods for selecting the optimal number of clusters in Python, 2020, URL: https://towardsdatascience.com/cheat-sheet-to-implementing-7-methodsfor-selecting-optimal-number-of-clusters-in-python-898241e1d6ad [7] B. Alam, Implementation of Hierarchical Clustering using Python, 2022, URL: https://handson.cloud/implementation-of-hierarchical-clustering-using-python/ [8] JM. Anaya, Y. Shoenfeld, A. Rojas-Villarraga, Autoimmunity: From Bench to Bedside, 2018,
Bogota, Colombia), URL: https://www.ncbi.nlm.nih.gov/books/NBK459443/ [9] PK. Nakane, A. Kawaoi, Peroxidase-labeled antibody. A new method of conjugation, Journal of
Histochemistry & Cytochemistry, 1974; 22(12), 1084-1091. https://doi.org/10.1177/22.12.1084 [10] R.Yu. Hrytsko, H.I. Bila, R.O. Bilyy, Test for coronavirus – what does it really means for the patient?, , Infectious Diseases, I.Horbachevsky Ternopil National Medical University, 2020, 6572, URL: https://ojs.tdmu.edu.ua/index.php/inf-patol/article/download/11287/10737/41013 [11] G. Lippi, A.-M. Simundic, M.Plebani, Potential preanalytical and analytical vulnerabilities in the laboratory diagnosis of coronavirus disease 2019 (COVID-19), Clinical Chemistry and Laboratory Medicine (CCLM), 2020, 58 (7), 1070-1076. https://doi.org/10.1515/cclm-2020-0285