On a problem of the reconstruction of distance matrices between DNA sequences

Abstract

In practice, quite often there is a need to calculate in a special way certain distances between sequences of different nature. Similar algorithms are used in bioinformatics to compare sequenced genetic chains. Due to the large dimension of such chains, it is necessary to use heuristic algorithms that give approximate results. There are various heuristic algorithms for determining the distance between genomes, but the obvious disadvantage in calculating the distance between the same pair of DNA strings is to obtain several different results when using different algorithms for calculating metrics.  Therefore, there is a problem of assessing the quality of the used metrics (distances), the results of which can be concluded about the applicability of the algorithm to various studies.In addition, one of the problems considered in biocybernetics is the problem of recovering the matrix of distances between DNA sequences, when not all elements of the considered matrix are known at the input of the algorithm. In this regard, a problem of developing method for comparative evaluation of algorithms calculating distances between sequences is used for another problem, i.e., the problem of restoring the matrix of distances between DNA sequences.In this article, we consider the possibility of using the developed and studied by us earlier method of comparative evaluation of algorithms for calculating distances between a pair of DNA strings to restore the partially filled matrix of distances. Matrix recovery occurs as a result of several computational passes. Estimation of unknown matrix elements are averaged in a special way with the use of so-called risk function, and the result of this averaging is considered asthe resulting value of the unknown element.