The application of the branch and bound method in the problem of reconstructing the matrix of distances between DNA strings

Abstract

In this paper, we continue to consider one of the tasks of biocybernetics, i.e. the problem of reconstructing the distance matrix between DNA sequences. In this problem, not all the elements of the matrix under consideration are known at the input of the algorithm (usually 50% or less of the elements). The basis for the development of the algorithm for reconstructing such a matrix is the method of comparative evaluation of algorithms for calculating distances between DNA sequences developed and investigated by us, based on a special analysis of the distance matrix. In this analysis, we applied the badness of each of the triangles of the matrix determined by us before. Continuing to improve the algorithms for solving this problem, we consider the use of the branches and bounds method in it. To do this, for some known sequence of unfilled elements, we apply the algorithms we considered in previous publications, but now we choose the sequences ourselves using developed by us version of method of branches and bounds. In our interpretation of this method, all possible sequences of unknown elements of the upper triangular part of the matrix are taken as the set of admissible solutions. In each current subtask, any of the blank elements of the matrix is taken as the separating element, and the sum of the badness values for all triangles that have already been formed by the time this subtask is considered is taken as the boundary. Thus, the definition of elements of an incompletely filled matrix occurs in such a sequence that the final badness indicator for all triangles is selected using greedy heuristics that fits completely into the framework of the classical variants of the description of the branches and bounds method. As a result of applying such an algorithm, we get results that, from the point of view of the value of badness, are the lowest possible (in the case of a completed version of the branch and boundary method), or close to optimal ones (in the case of its uncompleted version). At the same time, in our computational experiments, the running time of the algorithm practically coincides with the time of the algorithm considered by us in the previous publication (it exceeds it by no more than 10%), and the badness value usually decreases by 20-40% from the initial value. Thus, we are able to quickly and efficiently restore the DNA matrix, often even if it is filled less than 40%.