A Three-Stage Algorithm for the Closest String Problem on Artificial and Real Gene Sequences

• URL: http://arxiv.org/abs/2407.13023v1
• Date: Wed, 17 Jul 2024 21:26:27 GMT
• Title: A Three-Stage Algorithm for the Closest String Problem on Artificial and Real Gene Sequences
• Authors: Alireza Abdi, Marko Djukanovic, Hesam Tahmasebi Boldaji, Hadis Salehi, Aleksandar Kartelj,
• Abstract summary: Closest String Problem is an NP-hard problem that aims to find a string that has the minimum distance from all sequences that belong to the given set of strings. In this paper, we introduce a three-stage algorithm that comprises the following process: first, we apply a novel alphabet pruning method to reduce the search space for effectively finding promising search regions. Second, a variant of beam search to find a solution is employed. This method utilizes a newly developed guiding function based on an expected distance score of partial solutions.
• Score: 39.58317527488534
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Closest String Problem is an NP-hard problem that aims to find a string that has the minimum distance from all sequences that belong to the given set of strings. Its applications can be found in coding theory, computational biology, and designing degenerated primers, among others. There are efficient exact algorithms that have reached high-quality solutions for binary sequences. However, there is still room for improvement concerning the quality of solutions over DNA and protein sequences. In this paper, we introduce a three-stage algorithm that comprises the following process: first, we apply a novel alphabet pruning method to reduce the search space for effectively finding promising search regions. Second, a variant of beam search to find a heuristic solution is employed. This method utilizes a newly developed guiding function based on an expected distance heuristic score of partial solutions. Last, we introduce a local search to improve the quality of the solution obtained from the beam search. Furthermore, due to the lack of real-world benchmarks, two real-world datasets are introduced to verify the robustness of the method. The extensive experimental results show that the proposed method outperforms the previous approaches from the literature.

Related papers

• Fast Ergodic Search with Kernel Functions [0.4915744683251149]
  We develop a kernel-based ergodic metric and generalize it from Euclidean space to Lie groups. We derive the first-order optimality condition of the kernel ergodic metric for nonlinear systems. Comprehensive numerical benchmarks show that the proposed method is at least two orders of magnitude faster than the state-of-the-art algorithm.
  arXiv  Detail & Related papers  (2024-03-03T15:30:31Z)
• Best-$k$ Search Algorithm for Neural Text Generation [118.02691398555781]
  We propose a deterministic search algorithm balancing both quality and diversity. The proposed algorithm is parameter-free, lightweight, efficient, and easy to use.
  arXiv  Detail & Related papers  (2022-11-22T00:26:13Z)
• A Meta-Heuristic Search Algorithm based on Infrasonic Mating Displays in Peafowls [0.0]
  Simplistic methods such as exhaustive search become computationally expensive and unreliable as the solution space for search algorithms increase. This research proposes an Infrasonic Search Algorithm, inspired from the Gravitational Search Algorithm and the mating behaviour in peafowls.
  arXiv  Detail & Related papers  (2021-06-28T09:04:51Z)
• Determinantal Beam Search [75.84501052642361]
  Beam search is a go-to strategy for decoding neural sequence models. In use-cases that call for multiple solutions, a diverse or representative set is often desired. By posing iterations in beam search as a series of subdeterminant problems, we can turn the algorithm into a diverse subset selection process.
  arXiv  Detail & Related papers  (2021-06-14T13:01:46Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems [0.6882042556551609]
  This approach makes use of a algorithm to explore the search space tree of a problem instance. The algorithm is based on Monte Carlo tree search, a popular algorithm in game playing that is used to explore game trees.
  arXiv  Detail & Related papers  (2020-10-22T08:33:58Z)
• Evolutionary Algorithm and Multifactorial Evolutionary Algorithm on Clustered Shortest-Path Tree problem [2.578242050187029]
  Clustered Shortest-Path Tree Problem (CluSPT) is an NP-hard problem. To enhance the performance of the search process, two approaches are proposed.
  arXiv  Detail & Related papers  (2020-10-19T08:37:18Z)
• A Systematic Characterization of Sampling Algorithms for Open-ended Language Generation [71.31905141672529]
  We study the widely adopted ancestral sampling algorithms for auto-regressive language models. We identify three key properties that are shared among them: entropy reduction, order preservation, and slope preservation. We find that the set of sampling algorithms that satisfies these properties performs on par with the existing sampling algorithms.
  arXiv  Detail & Related papers  (2020-09-15T17:28:42Z)
• Best-First Beam Search [78.71330480725668]
  We show that the standard implementation of beam search can be made up to 10x faster in practice. We propose a memory-reduced variant of Best-First Beam Search, which has a similar beneficial search bias in terms of downstream performance.
  arXiv  Detail & Related papers  (2020-07-08T05:56:01Z)
• Improved Binary Artificial Bee Colony Algorithm [0.0]
  The Artificial Bee Colony (ABC) algorithm is an evolutionary optimization algorithm based on swarm intelligence. We improve the ABC algorithm to solve binary optimization problems and call it the improved binary Artificial Bee Colony (ibinABC) The proposed method consists of an update mechanism based on fitness values and processing different number of decision variables.
  arXiv  Detail & Related papers  (2020-03-12T17:22:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.