Some new heuristic algorithms in analysis of the similarity of DNA-sequences

Abstract

This paper describes algorithms, corresponding computer programs and the results of computations, supplementing results published earlier. We consider the multiple sequence alignment problem, which can be nominated by a central problem in computational biology. For it, we continue to consider some different versions of socalled “triangular norm” defined on the set of triangles formed by the different distance between genomes computed by different algorithms. Basically, the new results are associated with incorrect variants of obtaining the triangle inequality, which for matrices of the order of about 50 × 50 is violated in the two most successful metrics (including the Panin’s metric earlier developed by us) in less than 1% of cases. Possible improvements are related to the use of neural networks that were not used by us in previous calculations. In this case, neural networks solve the inverse problem: we improve (reduce) the overall badness of the matrix of distances between genomes, forcibly changing the previously obtained distances; further, we try to reflect these forced changes in the original algorithms for calculating distances. In this paper, we present the results of concrete calculations obtained by us.