Top

Published in:

2020 | OriginalPaper | Chapter

Different Approaches to Solving the Problem of Reconstructing the Distance Matrix Between DNA Chains

Authors : Boris Melnikov, Marina Trenina, Elena Melnikova

Published in: Modern Information Technology and IT Education

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, we consider one of the tasks of biocybernetics, i.e. the problem of reconstructing the distance matrix between DNA sequences. In this problem, not all the elements of the matrix under consideration are known at the input of the algorithm (usually 50% or less elements). The basis for the development of the algorithm for reconstructing such a matrix is the method of comparative evaluation of the algorithms for calculating distances between DNA sequences developed and investigated by us earlier. In this analysis, the badness of each of the triangles of the matrix determined by us was applied.

The restoration of the matrix occurs as a result of several computational passes. Estimates of unknown matrix elements are averaged in a special way using the risk function, and the result of this averaging is considered as the received value of the unknown element. To optimize the algorithm for solving this problem, we consider the use of the branch and bound method in it.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Integration and Development of Professionally-Oriented Social Network in the Context of the Evolution of the Information Landscape

next chapter Development of the Tools for Research of Transformation of Digital Objects Based on Generative Adversarial Networks

Toppi, J., et al.: A new statistical approach for the extraction of adjacency matrix from effective connectivity networks. In: 2013 35th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC), Osaka, pp. 2932–2935 (2013). https://doi.org/10.1109/embc.2013.6610154

Torshin, I.Yu.: Bioinformatics in the Post-Genomic Era: The Role of Biophysics. Nova Biomedical Books, New York (2006)

Van der Loo, M.P.J.: The stringdist package for approximate string matching. R J. 6(1), 111–122 (2014). https://doi.org/10.32614/RJ-2014-011CrossRef

Pages, H., Aboyoun, P., Gentleman, R., DebRaoy, S.: Biostrings: string objects representing biological sequences and matching algorithms. R package version 2.10.1 (2009)

Morgan, M., Lawrence, M.: ShortRead: base classes and methods for high-throughput short-read sequencing data. R package version 1.0.6 (2009)

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, pp. 360–364 (2016). https://elibrary.ru/item.asp?id=15292060

Eckes, B., Nischt, R., Krieg, T.: Cell-matrix interactions in dermal repair and scarring. Fibrogenesis Tissue Repair 3, 4 (2010). https://doi.org/10.1186/1755-1536-3-4CrossRef

Midwood, K.S., Williams, L.V., Schwarzbauer, J.E.: Tissue repair and the dynamics of the extracellular matrix. Int. J. Biochem. Cell Biol. 36(6), 1031–1037 (2004). https://doi.org/10.1016/j.biocel.2003.12.003CrossRef

Melnikov, B., Pivneva, S., Trifonov, M.: Comparative analysis of the algorithms of calculating distances of DNA sequences and some related problems. In: Proceedings of the III International Conference “Information Technology and Nanotechnology (ITNT 2017)”, pp. 1640–1645 (2017). https://elibrary.ru/item.asp?id=29267020

10.

Melnikov, B.: Heuristics in programming of nondeterministic games. Program. Comput. Softw. 27(5), 277–288 (2001). https://doi.org/10.1023/A:1012345111076MathSciNetCrossRefMATH

11.

Melnikov, B., Melnikova, E.: Approach to programming nondeterministic games (Part I: description of general heuristics). In: Proceedings of Higher Educational Institutions, Volga Region. Physics and Mathematics, vol. 4, no. 28, pp. 29–38 (2013). https://elibrary.ru/item.asp?id=21392713. (in Russian)

12.

Needleman, S., Wunsch, Ch.: A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol. 48(3), 443–453 (1970). https://doi.org/10.1016/0022-2836(70)90057-4CrossRef

13.

Hromkovič, J.: Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-662-05269-3CrossRefMATH

14.

Ayala, F.J., Kayger, J.: Modern Genetics. V. 1. Benjamin/Cummings Pub., Menlo Park (1980)

15.

Melnikov, B., Pivneva, S., Trifonov, M.: Various algorithms, calculating distances of DNA sequences, and some computational recommendations for use such algorithms. In: CEUR Workshop Proceedings, vol. 1902, pp. 43–50 (2017). https://doi.org/10.18287/1613-0073-2017-1902-43-50

16.

Appendix A. Matrices 28 × 28 and Additional Information. https://yadi.sk/i/JxAfi8jm3aEtEY

17.

Melnikov, B., Radionov, A., Moseev, A., Melnikova, E.: Some specific heuristics for situation clustering problems. In: ICSOFT, Technologies, Proceedings 1st International Conference on Software and Data Technologies, pp. 272–279 (2006). https://elibrary.ru/item.asp?id=15292004

Title: Different Approaches to Solving the Problem of Reconstructing the Distance Matrix Between DNA Chains
Authors: Boris Melnikov
Marina Trenina
Elena Melnikova
Publisher: Springer International Publishing
Book: Modern Information Technology and IT Education
Print ISBN: 978-3-030-46894-1

Electronic ISBN: 978-3-030-46895-8

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-46895-8_17

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner