論文の概要: A Learning Search Algorithm for the Restricted Longest Common Subsequence Problem

• arxiv url: http://arxiv.org/abs/2410.12031v1
• Date: Tue, 15 Oct 2024 20:02:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-17 13:42:28.952189
• Title: A Learning Search Algorithm for the Restricted Longest Common Subsequence Problem
• Title（参考訳）: 制限付き長文列問題に対する学習探索アルゴリズム
• Authors: Marko Djukanović, Jaume Reixach, Ana Nikolikj, Tome Eftimov, Aleksandar Kartelj, Christian Blum,
• Abstract要約: RLCS問題(Restricted Longest Common Subsequence)はバイオインフォマティクスにおいて重要な応用である。 本稿では,将来性のある地域に向けて,探索プロセスを強化するための2つの新しいアプローチを提案する。 この論文の重要な貢献は、科学的な抽象が入力文字列として機能する実世界のインスタンスの生成である。
• 参考スコア（独自算出の注目度）: 40.64116457007417
• License:
• Abstract: This paper addresses the Restricted Longest Common Subsequence (RLCS) problem, an extension of the well-known Longest Common Subsequence (LCS) problem. This problem has significant applications in bioinformatics, particularly for identifying similarities and discovering mutual patterns and important motifs among DNA, RNA, and protein sequences. Building on recent advancements in solving this problem through a general search framework, this paper introduces two novel heuristic approaches designed to enhance the search process by steering it towards promising regions in the search space. The first heuristic employs a probabilistic model to evaluate partial solutions during the search process. The second heuristic is based on a neural network model trained offline using a genetic algorithm. A key aspect of this approach is extracting problem-specific features of partial solutions and the complete problem instance. An effective hybrid method, referred to as the learning beam search, is developed by combining the trained neural network model with a beam search framework. An important contribution of this paper is found in the generation of real-world instances where scientific abstracts serve as input strings, and a set of frequently occurring academic words from the literature are used as restricted patterns. Comprehensive experimental evaluations demonstrate the effectiveness of the proposed approaches in solving the RLCS problem. Finally, an empirical explainability analysis is applied to the obtained results. In this way, key feature combinations and their respective contributions to the success or failure of the algorithms across different problem types are identified.
• Abstract（参考訳）: 本稿では、有名なLongest Common Subsequence(LCS)問題の拡張であるRestricted Longest Common Subsequence(RLCS)問題に対処する。 この問題はバイオインフォマティクス、特に類似性を同定し、DNA、RNA、タンパク質配列間の相互パターンや重要なモチーフを発見するために重要な応用がある。 本稿では, 一般探索フレームワークによるこの問題の解決の最近の進歩を基盤として, 探索空間における将来性のある領域に向けて, 探索プロセスを強化するための2つの新しいヒューリスティックアプローチを提案する。 最初のヒューリスティックは、探索過程における部分解を評価する確率モデルを用いている。 第2のヒューリスティックは、遺伝的アルゴリズムを使用してオフラインでトレーニングされたニューラルネットワークモデルに基づいている。 このアプローチの重要な側面は、部分解と完全な問題インスタンスの問題を抽出することである。 トレーニングされたニューラルネットワークモデルとビームサーチフレームワークを組み合わせることにより、学習ビームサーチと呼ばれる効果的なハイブリッド手法を開発した。 本論文の重要な貢献は,科学的な抽象語が入力文字列として機能する実世界の事例の生成であり,文献からの頻繁な学術用語の集合が制約パターンとして使用される。 総合的な実験的評価は、RCCS問題の解法における提案手法の有効性を示すものである。 最後に、得られた結果に経験的説明可能性分析を適用する。 このようにして、重要な特徴の組み合わせと、異なる問題タイプにわたるアルゴリズムの成功や失敗に対するそれぞれの貢献が特定される。

関連論文リスト

• Guiding Genetic Programming with Graph Neural Networks [0.20718016474717196]
  本稿では,記号回帰問題から付加的な知識を引き出すためにグラフニューラルネットワークを用いたEvoNUDGEを提案する。 多数の問題インスタンスに対する広範な実験では、EvoNUDGEは複数のベースラインを大幅に上回っている。
  論文  参考訳（メタデータ） (2024-11-03T20:43:31Z)
• Early years of Biased Random-Key Genetic Algorithms: A systematic review [2.249916681499244]
  本稿では,Biased Random-Key Genetic Algorithms(BRKGA)に着目した系統的な文献レビューと文献分析を行う。 BRKGAは、遺伝的アルゴリズムとともにバイアス付き、均一でエリート的な交配戦略を持つランダムキーベースの染色体を使用するメタヒューリスティックなフレームワークである。
  論文  参考訳（メタデータ） (2024-05-02T22:22:41Z)
• Solving the vehicle routing problem with deep reinforcement learning [0.0]
  本稿では,NP-Hard 問題のクラスに属する有名な問題である Vehicle Routing Problem (VRP) に対する RL の適用について述べる。 第2フェーズでは、アクターと批評家の背後にあるニューラルアーキテクチャが確立され、畳み込みニューラルネットワークに基づいたニューラルアーキテクチャを採用することが選択された。 広範囲なインスタンスで行った実験では、アルゴリズムが優れた一般化能力を持ち、短時間で良い解に達することが示されている。
  論文  参考訳（メタデータ） (2022-07-30T12:34:26Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。 頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。 特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
  論文  参考訳（メタデータ） (2022-01-18T11:16:40Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。 本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。 ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
  論文  参考訳（メタデータ） (2021-12-03T14:23:05Z)
• An LSTM-based Plagiarism Detection via Attention Mechanism and a Population-based Approach for Pre-Training Parameters with imbalanced Classes [1.9949261242626626]
  本稿では,Long Short-Term Memory(LSTM)と,LSTM-AM-ABCと呼ばれるアテンション機構に基づくアーキテクチャを提案する。 提案アルゴリズムは,全てのLSTM,アテンション機構,フィードフォワードニューラルネットワークにおいて,モデル学習の初期値を同時に求めることができる。
  論文  参考訳（メタデータ） (2021-10-17T09:20:03Z)
• Consistency of mechanistic causal discovery in continuous-time using Neural ODEs [85.7910042199734]
  ダイナミカルシステムの研究において,連続時間における因果的発見を検討する。 本稿では,ニューラルネットワークを用いた因果探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-06T08:48:02Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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