?
An efficient approach to the protein structure alignment problem
The Protein Structure Alignment Problem (PSAP) consists in finding the
best alignment of two proteins defined by their primary structures. It finds
the most similar substructure of two proteins. This problem is polynomially
reducible to the Maximum Clique Problem (MCP) for the protein alignment
graph. In this paper we present an efficient algorithm for the PSAP based on
our recent ILS&MCS algorithm (Batsyn et al., 2014) for the MCP. To reduce
the alignment problem to the MCP we follow the DAST method introduced
by Malod-Dognin et al. (2010). Our main contributions include: applying the
ILS heuristic to obtain a lower bound and make preprocessing of an alignment
graph to reduce its size; efficient implementation of the algorithm for large but
sparse alignment graphs including memory preallocation and bit representation
of adjacency matrix. The computational results are provided for the popular
Skolnick test set of 40 proteins and show that the suggested algorithm is more
efficient than one of the fastest PSAP solvers - the ACF algorithm by Malod-
Dognin et al. (2010).
Priority areas:
IT and mathematics
Language:
English
Publication based on the results of:
Ulyanov M., Fomichev M., Головешкин В. А. et al., 2017 Т. 13 № 1 С. 19-24
The complexity of the individual traveling salesman problem was analyzed by means of mathematical statistics. The complexity is defined as a number of nodes of the decision tree created by the branch and bound algorithm. We obtained approximate representations for parameters of probability distribution of the natural logarithm of the complexity. These representations are functions ...
Added: September 26, 2017
Mikhail Batsyn, Boris Goldengorin, Evgeny Maslov et al., Journal of Combinatorial Optimization 2014 Vol. 27 No. 2 P. 397-416
In this paper we present improvements to one of the most recent and fastest branch-and-bound algorithm for the maximum clique problem—MCS algorithm by Tomita et al. (Proceedings of the 4th international conference on Algorithms and Computation, WALCOM’10, pp. 191–203, 2010). The suggested improvements include: incorporating of an efficient heuristic returning a high-quality initial solution, fast ...
Added: February 17, 2013
San Segundo P., Nikolaev A., Batsyn M., Computers & Operations Research 2015 Vol. 64 P. 293-303
Many efficient exact branch and bound maximum clique solvers use approximate coloring to compute an upper bound on the clique number for every subproblem. This technique reasonably promises tight bounds on average, but never tighter than the chromatic number of the graph.
Li and Quan, 2010, AAAI Conference, p. 128–133 describe a way to compute even ...
Added: August 24, 2015
Ignatov A., Andrei Gorchakov, Open Computer Science 2020 Vol. 10 No. 1 P. 112-116
The paper describes a simulator of parallel Branch and Bound (BnB) method. Several subdomain trees for benchmark functions are analyzed, a characteristic Gaussian-like distribution is discovered. An algorithm of artificial tree generation is formulated according to this criterion. The process of simulator modeling is described, several computational experiments are conducted. Their results show a hyperbolic ...
Added: June 11, 2020
Babash A. V., М. : ИНФРА-М, РИОР, 2013
Пособие предназначено для студентов высших учебных заведений, обучающихся по специальности «Прикладная информатика (в экономике)». Оно также содержит методический материал для ряда инновационных курсов лекций по профилю «Информационная безопасность» и может быть использовано и для блока дисциплин этого профиля. Ряд представленных результатов полезен специалистам и аспирантам, специализирующихся в указанной области. ...
Added: January 14, 2014
Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 4 С. 66-72
Рассматривается конструктивный подход к формированию новых случаев эффективной разрешимости задачи о независимом множестве в семействе наследственных частей множества графов Free({P5,C5}). Именно, доказывается, что если эта задача полиномиально разрешима в классе Free({P5,C5,G}), то для любого графа H, который может быть индуктивно получен из G применением к текущему графу сложения с K1 или умножения на K1, эта ...
Added: August 31, 2012
Yasnitsky L., Пермь : Пермский государственный национальный исследовательский университет. – Электронные данные. , 2020
The collection contains materials from the international conference "Intelligent systems in science and technology" and the Sixth all-Russian scientific and practical conference "Artificial intelligence in solving urgent social and economic problems of the XXI century", which was held on October 12-18, 2020 in Perm as part of the Perm natural science forum "Mathematics and global ...
Added: December 4, 2020
Пермь : Пермский государственный национальный исследовательский университет, 2020
В сборнике представлены статьи участников Всероссийской научно-практической конференции молодых ученых с международным участием «Математика и междисциплинарные исследования – 2020». На конференцию было прислано более ста статей из различных регионов России, а также из ближнего
и дальнего зарубежья. По итогам работы экспертной комиссии для публикации было отобрано шестьдесят две статьи. Каждая статья оценивалась группой экспертов в той области, которая рассматривается автором.
Представленные ...
Added: December 10, 2020
Springer, 2021
This book constitutes the proceedings of the 16th International Conference on Formal Concept Analysis, ICFCA 2021, held in Strasbourg, France, in June/July 2021.
The 14 full papers and 5 short papers presented in this volume were carefully reviewed and selected from 32 submissions. The book also contains four invited contributions in full paper length.
The research part ...
Added: July 10, 2021
Koldanov A. P., Koldanov P., Semenov D., Журнал Новой экономической ассоциации 2021 Т. 2 № 50 С. 12-34
. The problem of analysis of pairwise connections between stocks of financial market by observations on stock returns is considered. Such problem arise in stock market network analysis. It is assumed that joint distribution of stock returns belongs to the wide class of elliptical distributions. Classical Pearson correlation, Fechner correlation and Kendall correlation are used ...
Added: June 17, 2021
Barcelona : IEEE, 2017
International Conference on Control, Decision and Information Technologies. ...
Added: January 17, 2018
Vostrikov A. V., Borisov N., Abrameshin A. E., Качество. Инновации. Образование 2013 № 8 (99) С. 61-65
In work research of numerical stability of earlier reduced scheme of numerical integration of system of the linear ordinary differential equations developed by authors is conducted. The received condition of numerical stability of the reducing scheme proves possibility of use of this scheme in practice. Operability of the reduced scheme was tested on a real ...
Added: September 9, 2013
Красноярск : ИВМ СО РАН, 2013
Труды Пятой Международной конференции «Системный анализ и информационные технологии» САИТ-2013 (19–25 сентября 2013 г., г.Красноярск, Россия): ...
Added: November 18, 2013
Bliznets Ivan, Cygan M., Komosa P. et al., ACM Transactions on Computation Theory 2018 Vol. 10 No. 2 P. 1-32
The H-free Edge Deletion problem asks, for a given graph G and integer k, whether it is possible to delete at most k edges from G to make it H-free—that is, not containing H as an induced subgraph. The H-free Edge Completion problem is defined similarly, but we add edges instead of deleting them. The study of these two problem families has recently been the subject of intensive studies from the point of ...
Added: October 30, 2018
Marshirov V. V., Marshirova L. E., Сибирский журнал индустриальной математики 2013 Т. XVI № 4 С. 111-120
The paper considers the problem of determining the rate of cooling of metal during solidification at the intersection of the liquidus temperature under intense heat sink from the surface. The solution to this problem it is necessary to determine the process conditions, the boundary and initial conditions for which it is possible to get new ...
Added: November 17, 2013
Akopov A. S., Beklaryan L. A., Saghatelyan A. K., Environmental Modelling and Software 2019 Vol. 116 P. 7-25
Urban greenery such as trees can effectively reduce air pollution in a natural and eco-friendly way. However, how to spatially locate and arrange greenery in an optimal way remains as a challenging task. We developed an agent-based model of air pollution dynamics to support the optimal allocation and configuration of tree clusters in a city. The Pareto ...
Added: February 24, 2019
Chernyshev S. V., Cherepanov E. A., Pankratiev E. V. et al., Journal of Mathematical Sciences 2005 Vol. 128 No. 6 P. 3487-3495
Added: January 27, 2014
P. : Université Paris 13 - Paris Sorbonne Cité, 2013
In this workshop we will bring together participants who have solutions for one or more of the following problems: How can mutual understanding be optimized with the help of technology in hospitals where both patients and professionals have varying language skills, cultural backgrounds and cognitive capacities? Can domain ontologies, natural language processing tools, multilingual knowledge-based ...
Added: December 18, 2014
Beklemishev L. D., Оноприенко А. А., Математический сборник 2015 Т. 206 № 9 С. 3-20
We formulate some term rewriting systems in which the number of computation steps is finite for each output, but this number cannot be bounded by a provably total computable function in Peano arithmetic PA. Thus, the termination of such systems is unprovable in PA. These systems are derived from an independent combinatorial result known as the Worm ...
Added: March 13, 2016
Lanham : University Press of America, 2012
The history of logic and analytic philosophy in Central and Eastern Europe is still known to very few people. As an exception to the rule, only two scientific schools became internationally popular: the Vienna Circle and the Lvov-Warsaw School. Nevertheless, the countries included in this region have not only joint history, but also joint cultural ...
Added: February 13, 2013
Furmanov K. K., Nikol'skii I. M., Computational Mathematics and Modeling 2016 Vol. 27 No. 2 P. 247-253
Added: December 22, 2016
Yasnitsky L., Ваулева С. В., Сафонова Д. Н. et al., Всероссийский криминологический журнал 2015 Т. 9 № 3 С. 423-430
Modern criminalists do not share a common opinion regarding the choice of parameters which could be used to work out a system of characteristics to differentiate a maniac killer from an ordinary person. This hinders the development of efficient software for investigation purposes. The paper describes the experience of developing a neural network that can ...
Added: October 1, 2015
Vyalyi M., Дискретная математика 1991 Т. 3 № 3 С. 35-45
Added: October 17, 2014
Skoptsov K. A., Sheshenin S., Galatenko V. V. et al., International Journal of Applied Mechanics 2016 Vol. 8 No. 2 P. 1650016-01-1650016-18
We present a method for evaluating elastic properties of a composite material produced by molding a resin filled with short elastic fibers. A flow of the filled resin is simulated numerically using a mesh-free method. After that, assuming that spatial distribution and orientation of fibers are not significantly changed during polymerization, effective elastic moduli of ...
Added: May 22, 2016