論文の概要: A Three-Stage Algorithm for the Closest String Problem on Artificial and Real Gene Sequences

• arxiv url: http://arxiv.org/abs/2407.13023v1
• Date: Wed, 17 Jul 2024 21:26:27 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-19 19:23:28.029472
• Title: A Three-Stage Algorithm for the Closest String Problem on Artificial and Real Gene Sequences
• Title（参考訳）: 人工及び実遺伝子列上の最接近文字列問題に対する3段階アルゴリズム
• Authors: Alireza Abdi, Marko Djukanovic, Hesam Tahmasebi Boldaji, Hadis Salehi, Aleksandar Kartelj,
• Abstract要約: ストロースト文字列問題(Closest String Problem)は、与えられた文字列の集合に属するすべての列から最小距離の文字列を見つけることを目的としたNPハード問題である。 本稿では,次の3段階のアルゴリズムを提案する。まず,検索領域を効果的に見つけるために,検索空間を削減するために,新しいアルファベットプルーニング手法を適用する。 第二に、解を見つけるためのビーム探索の変種を用いる。この方法は、部分解の期待距離スコアに基づいて、新たに開発された誘導関数を利用する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 最も近い文字列問題 (Closest String problem) は、与えられた文字列の集合に属するすべての列から最小距離の文字列を見つけることを目的としたNPハード問題である。 その応用は、符号化理論、計算生物学、デジェネレーションプライマーの設計などに見ることができる。 二進数列に対する高品質な解に到達した効率的な正確なアルゴリズムがある。 しかし、DNAとタンパク質配列に対する解の質に関してはまだ改善の余地がある。 本稿では,次の3段階のアルゴリズムを提案する。まず,検索領域を効果的に見つけるために,検索空間を削減するために,新しいアルファベットプルーニング手法を適用する。 第二に、ヒューリスティックな解を見つけるためにビームサーチの変種を用いる。 本手法は, 部分解の期待距離ヒューリスティックスコアに基づいて, 新たに開発された誘導関数を利用する。 最後に,ビームサーチから得られる解の質を向上させるために,局所探索を導入する。 さらに、実世界のベンチマークが欠如しているため、この手法の堅牢性を検証するために、2つの実世界のデータセットが導入された。 実験結果から,提案手法が従来の手法よりも優れていたことが示唆された。

関連論文リスト

• Fast Ergodic Search with Kernel Functions [0.4915744683251149]
  カーネルベースのエルゴード計量を開発し、ユークリッド空間からリー群へ一般化する。 非線形システムに対するカーネルエルゴード計量の1次最適条件を導出する。 総合的な数値ベンチマークにより、提案手法は最先端のアルゴリズムよりも少なくとも2桁高速であることが示された。
  論文  参考訳（メタデータ） (2024-03-03T15:30:31Z)
• Best-$k$ Search Algorithm for Neural Text Generation [118.02691398555781]
  本稿では,品質と多様性のバランスをとる決定論的探索アルゴリズムを提案する。 提案アルゴリズムはパラメータフリーで、軽量で、効率的で、使いやすくなっている。
  論文  参考訳（メタデータ） (2022-11-22T00:26:13Z)
• A Meta-Heuristic Search Algorithm based on Infrasonic Mating Displays in Peafowls [0.0]
  探索アルゴリズムの解空間が増大するにつれて、網羅的探索のような単純な手法は計算コストが高く、信頼性が低いものとなる。 本研究では, 重力探索アルゴリズムとオオカミの交尾行動から着想を得た赤外探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-28T09:04:51Z)
• Determinantal Beam Search [75.84501052642361]
  ビームサーチは、ニューラルシーケンスモデルをデコードするためのゴーツー戦略である。 複数のソリューションを要求するユースケースでは、多様あるいは代表的なセットがしばしば望まれる。 ビームサーチを一連の部分決定問題として繰り返し行うことにより、アルゴリズムを多種多様なサブセット選択プロセスに変換することができる。
  論文  参考訳（メタデータ） (2021-06-14T13:01:46Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems [0.6882042556551609]
  このアプローチでは,問題インスタンスの探索空間木を探索するアルゴリズムを用いる。 このアルゴリズムはモンテカルロ木探索(Monte Carlo tree search)をベースとしている。
  論文  参考訳（メタデータ） (2020-10-22T08:33:58Z)
• Evolutionary Algorithm and Multifactorial Evolutionary Algorithm on Clustered Shortest-Path Tree problem [2.578242050187029]
  CluSPT(Clustered Shortest-Path Tree Problem)はNPハード問題である。 探索処理の性能を向上させるために,2つの手法を提案する。
  論文  参考訳（メタデータ） (2020-10-19T08:37:18Z)
• A Systematic Characterization of Sampling Algorithms for Open-ended Language Generation [71.31905141672529]
  本稿では,自己回帰型言語モデルに広く採用されている祖先サンプリングアルゴリズムについて検討する。 エントロピー低減, 秩序保存, 斜面保全の3つの重要な特性を同定した。 これらの特性を満たすサンプリングアルゴリズムのセットが,既存のサンプリングアルゴリズムと同等に動作することがわかった。
  論文  参考訳（メタデータ） (2020-09-15T17:28:42Z)
• Best-First Beam Search [78.71330480725668]
  本研究では,ビームサーチの標準実装を10倍高速に実現可能であることを示す。 ダウンストリーム性能の面でも同様に有益な探索バイアスを有するBest-First Beam Searchのメモリ再生版を提案する。
  論文  参考訳（メタデータ） (2020-07-08T05:56:01Z)
• Improved Binary Artificial Bee Colony Algorithm [0.0]
  Artificial Bee Colony (ABC)アルゴリズムは、Swarmインテリジェンスに基づく進化的最適化アルゴリズムである。 我々はABCアルゴリズムを改良してバイナリ最適化問題を解き、それを改良されたバイナリ・ビーコロニー (ibinABC) と呼ぶ。 提案手法は,適合度値に基づく更新機構と,異なる数の決定変数の処理により構成される。
  論文  参考訳（メタデータ） (2020-03-12T17:22:52Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。