TY - JOUR

T1 - AN INVERSE PROBLEM FOR MATRIX PROCESSING

T2 - AN IMPROVED ALGORITHM FOR RESTORING THE DISTANCE MATRIX FOR DNA CHAINS

AU - Melnikov, Boris

AU - Zhang, Ye

AU - Chaikovskii, Dmitrii

N1 - Publisher Copyright:
© 2022, Institute for Problems in Mechanical Engineering, Russian Academy of Sciences. All rights reserved.

PY - 2022

Y1 - 2022

N2 - We consider one of the cybernetic methods in biology related to the study of DNA chains. Namely, we are considering the problem of reconstructing the distance matrix for DNA chains. Such a matrix is formed on the basis of any of the possible algorithms for determining the distances between DNA chains. The objects of research of these algorithms (for mammals), as a rule, are one of the following 3 variants: the main histocompatibility complex, the mitochondrial DNA, and “the tail” of the Y chromosome. In the paper we give an improved algorithm for restoring the distance matrix for DNA chains. Compared to our previous publications, the following changes have been made to the algorithm. We abandoned the use of the branches and bounds method, but at the same time significantly improved the greedy auxiliary algorithm used in it. In this paper, we apply only this greedy algorithm to the general solution of the distance matrix reconstruction problem. As a result of the conducted computational experiments carried out on one of the two considered criteria for the quality of the algorithms, significant improvements were obtained compared to the results given in our previous publications. At the same time, the total running time of the algorithm remained almost the same as in the previous version.

AB - We consider one of the cybernetic methods in biology related to the study of DNA chains. Namely, we are considering the problem of reconstructing the distance matrix for DNA chains. Such a matrix is formed on the basis of any of the possible algorithms for determining the distances between DNA chains. The objects of research of these algorithms (for mammals), as a rule, are one of the following 3 variants: the main histocompatibility complex, the mitochondrial DNA, and “the tail” of the Y chromosome. In the paper we give an improved algorithm for restoring the distance matrix for DNA chains. Compared to our previous publications, the following changes have been made to the algorithm. We abandoned the use of the branches and bounds method, but at the same time significantly improved the greedy auxiliary algorithm used in it. In this paper, we apply only this greedy algorithm to the general solution of the distance matrix reconstruction problem. As a result of the conducted computational experiments carried out on one of the two considered criteria for the quality of the algorithms, significant improvements were obtained compared to the results given in our previous publications. At the same time, the total running time of the algorithm remained almost the same as in the previous version.

KW - DNA chains

KW - distance matrix

KW - greedy algorithm

KW - heuristics

KW - optimization problem

KW - restoring algorithm

UR - http://www.scopus.com/inward/record.url?scp=85146831050&partnerID=8YFLogxK

U2 - 10.35470/2226-4116-2022-11-4-217-226

DO - 10.35470/2226-4116-2022-11-4-217-226

M3 - Article

AN - SCOPUS:85146831050

SN - 2223-7038

VL - 11

SP - 217

EP - 226

JO - Cybernetics and Physics

JF - Cybernetics and Physics

IS - 4

ER -