Реализация метода ветвей и границ для задачи восстановления матрицы расстояний между последовательностями ДНК
Authors: АБРАМЯН М Э. , МЕЛЬНИКОВ Б Ф. , ТРЕНИНА М А. 
Published: January 2025

В биоинформатике имеются две важные задачи для исследования эволюционных процессов: вычисление расстояния между последовательностями ДНК и восстановление матрицы расстояний между такими последовательностями для различных геномов, когда известны не все элементы этой матрицы. В силу большой размерности цепочек ДНК для решения первой задачи используются эвристические алгоритмы. Их основной недостаток состоит в том, что при использовании различных эвристических алгоритмов для вычисления расстояния между одной и той же парой цепочек ДНК получаются различные значения.  Для проведения сравнительного анализа этих эвристических алгоритмов был введён показатель badness для всех треугольников, образующихся в матрице ДНК, и в идеале он должен быть равен нулю. Этот показатель использовался в дальнейшем и для решения второй задачи. На основе того, что показатель badness должен быть равен нулю, разработан алгоритм восстановления матрицы расстояний между цепочками ДНК. Этот алгоритм оптимизирован применением в нём метода ветвей и границ. С помощью описываемого нами варианта этого метода выбирается такая последовательность вычисления неизвестных элементов, при которой значение показателя badness матрицы будет наименьшим.  Часть статьи посвящена подробному описанию алгоритмов. Самым важным среди вспомогательных алгоритмов является алгоритм выбора разделяющего элемента, т.е. того из неизвестных элементов, который мы восстанавливаем в первую очередь. Основной алгоритм, т.е. собственно восстановление матрицы ДНК методом ветвей и границ, включает описание задачи, состоящей из подзадач; каждая из последних является набором из преобразованной матрицы, последовательности уже восстановленных элементов исходной матрицы и множества тех ещё не заполненных элементов матрицы, которые нельзя выбирать на следующем шаге алгоритма. В статье также приведено описание программной реализации описанных алгоритмов.

Bioinformatics has two important problems for the study of evolutionary processes: calculating the distance between DNA sequences and restoring a matrix of distances sequences of different genomes when not all initial elements are known. Due to the large dimension of DNA chains, heuristic algorithms are used to solve the first problem. The main lack of them is that when using different heuristic algorithms to calculate the distance between the same pair DNA chains, we produce different values. To make a comparative analysis of these heuristic algorithms, a badness index was introduced for all the triangles formed in the DNA matrix, and ideally it should be zero. This indicator was used in the future and to solve the second problem. Based on the fact that the badness indicator should be equal to zero, the algorithm of restoring the matrix of distances between DNA chains is developed. This algorithm is optimized using the branch and bound method. This method selects a sequence of calculations of unknown elements, in which the value of the badness matrix will be the smallest. A part of the paper is devoted to the detailed description of algorithms. The most important among the auxiliary algorithms is the algorithm for selecting the separating element, i.e. the unknown element, which we recover first. The main algorithm, i.e. the actual recovering the DNA matrix by the method of branch and bound, includes a description of the task, which consists of subtasks containing a set of the transformed matrix, a sequence of already restored elements of the original matrix and the set of those not yet filled elements of the matrix, which cannot be selected in the next step of the algorithm. The paper also includes the program implementation of the described algorithms.