ipmash@ipme.ru | +7 (812) 321-47-78
пн-пт 10.00-17.00
Институт Проблем Машиноведения РАН ( ИПМаш РАН ) Институт Проблем Машиноведения РАН ( ИПМаш РАН )

МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное учреждение науки
Институт проблем машиноведения Российской академии наук

МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное учреждение науки
Институт проблем машиноведения Российской академии наук

An inverse problem for matrix processing: an improved algorithm for restoring the distance matrix for DNA chains

Авторы:
Boris Melnikov , Ye Zhang , Dmitrii Chaikovskii ,
Страницы:
217–226
Аннотация:

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.

Файл (pdf):
02:26
611
Используя этот сайт, вы соглашаетесь с тем, что мы используем файлы cookie.