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

Boris Melnikov, Marina Trenina

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.

Full Text:

PDF (Russian)

References


Ajala F., Kajger Dzh. Sovremennaja genetika. Per. s angl. T. 1. –

M.: Mir. 1987. 295 s.

Mel'nikov B. F., Romanov N. V. Eshhjo raz ob jevristikah dlja zadachi

kommivojazhjora. Teoreticheskie problemy informatiki i ee pri-

lozhenij. T. 4. 2001. S. 81–86.

Melnikov B., Radionov A., Gumayunov V. Some special heuristics

for discrete optimization problems. In: Proceedings of 8th International

Conference on Enterprise Information Systems, ICEIS-2006. Paphos.

P. 360–364.

Mel'nikov B. F., Panin A. G. Parallel'naja realizacija mul'ti-

jevristicheskogo podhoda v zadache sravnenija geneticheskih posle-

dovatel'nostej. Vektor nauki Tol'jattinskogo gosudarstvennogo

universiteta. # 4 (22). 2012. S. 83–86.

Mel'nikov B. F., Pivneva S. V, Trifonov M. A. Mul'tijevristi-

cheskij podhod k sravneniju kachestva opredeljaemyh metrik na

mnozhestve posledovatel'nostej DNK. Sovremennye informaci-

onnye tehnologii i IT obrazovanie. T. 13. # 2. 2017. S. 89–96.

Eckes B., Nischt R., Krieg T. Cell-matrix interactions in dermal

repair and scarring. Fibrogenesis Tissue Repair. No. 3:4. 2010.

doi:10.1186/1755-1536-3-4.

Midwood K. S., Williams L. V., Schwarzbauer J. E. Tissue repair and

the dynamics of the extracellular matrix. The International Journal of

Biochemistry & Cell Biology. 2004. Vol. 36. Issue 6. P. 1031–1037.

Mel'nikov B. F., Radionov A. N. O vybore strategii v nedeter-

mirovannyh antagonisticheskih igrah. Programmirovanie. # 5.

S. 55–62.

Mel'nikov B. F. Jevristiki v programmirovanii nedeterminiro-

vannyh igr. Izvestija RAN. Programmirovanie. # 5. 2001. S. 63–80.

Gjeri M., Dzhonson M. Vychislitel'nye mashiny i trudnoreshae-

mye zadachi. Per. s angl. – M.: Mir. 1982. 416 s.

Needleman S., Wunsch Ch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology. 1970. Vol. 48. No. 3. P. 443–453.

Kormen T., Lejzerson Ch., Rivest R., Shtajn K. Algoritmy. Po-

stroenie i analiz. M.: Vil'jams, 2005. 1296 s.

Pages H., Aboyoun P., Gentleman R., DebRaoy S. Biostrings: String

Objects Representing Biological Sequences and Matching Algorithms

[Jelektron. resurs]. Bioconductor – Jelektron. dan. – Rezhim dostu-

pa: https://bioc.ism.ac.jp/packages/2.6/bioc/html/Biostrings.html, svo-

bodnyj

Frans B. M. Bonobo: The Forgotten Ape. University of California

Press, ISBN 0-520-20535-9; trade paperback. October. 1998. P. 224.

Melnikov B. F., Pivneva S. V., Trifonov M. A. Comparative analysis

of algorithms calculating distances of DNA sequences and some related

problems. Sbornik trudov III mezhdunarodnoj konferencii i mo-

lodezhnoj shkoly «Informacionnye tehnologii i nanotehnologii

(ITNT-2017)», Samarskij nacional'nyj issledovatel'skij uni-

versitet imeni akademika S.P. Koroleva. 2017. S. 1640–1645.

Melnikov B. Heuristics in programming of nondeterministic games.

Programming and Computer Software. Vol. 27. No. 5. 2001. S. 277–

Mel'nikov B. F., Mel'nikova E. A. Podhod k programmirovaniju

nedeterminirovannyh igr (Chast' I: Opisanie obshhih jevristik).

Izvestija vysshih uchebnyh zavedenij. Povolzhskij region. Fiziko-

matematicheskie nauki. # 4 (28). 2013. S. 29–38.

Mel'nikov B. F., Pivneva S. V. Prinjatie reshenij v prikladnyh

zadachah s primeneniem dinamicheski podobnyh funkcij riska.

Vestnik transporta Povolzh'ja. # 3. 2010. S. 28–33.

Mel'nikov B. F., Trenina M. A., Kochergin A. S. Podhod k uluch-

sheniju algoritmov raschjota rasstojanij mezhdu cepochkami DNK

(na primere algoritma Nidlmana – Vunsha). Izvestija vysshih

uchebnyh zavedenij. Povolzhskij region. Fiziko-matematicheskie

nauki. # 1 (45). 2018. (https://izvuz_fmn.pnzgu.ru/fmn118)

Home – Nucleotide – NCBI [Jelektron. resurs]. – Rezhim dostupa:

https://www.ncbi.nlm.nih.gov/nuccore, svobodnyj

Makarkin S., Melnikov B., Panin A. On the metaheuristics approach

to the problem of genetic sequence comparison and its parallel

implementation. Applied Mathematics (Scientific Research Publishing).

Vol. 04. No. 10. P. 35–39.


Refbacks

  • There are currently no refbacks.


Abava   IEEE FRUCT 2018

ISSN: 2307-8162