論文の概要: On Solving the Multiple Variable Gapped Longest Common Subsequence Problem

• arxiv url: http://arxiv.org/abs/2604.18645v1
• Date: Sun, 19 Apr 2026 21:44:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-22 22:41:49.382914
• Title: On Solving the Multiple Variable Gapped Longest Common Subsequence Problem
• Title（参考訳）: 複数変数のGapped Longest Common Subsequence問題の解法について
• Authors: Marko Djukanović, Nikola Balaban, Christian Blum, Aleksandar Kartelj, Sašo Džeroski, Žiga Zebec,
• Abstract要約: 本稿では,可変Gapped Longest Common Subsequence問題に対処する。 これは、連続解の文字間のフレキシブルなギャップ制約を含む古典的LCS問題の一般化である。 本稿では,ルートベース状態グラフ表現に基づく検索フレームワークを提案する。
• 参考スコア（独自算出の注目度）: 36.85666459036717
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper addresses the Variable Gapped Longest Common Subsequence (VGLCS) problem, a generalization of the classical LCS problem involving flexible gap constraints between consecutive solutions' characters. The problem arises in molecular sequence comparison, where structural distance constraints between residues must be respected, and in time-series analysis where events are required to occur within specified temporal delays. We propose a search framework based on the root-based state graph representation, in which the state space comprises a generally large number of rooted state subgraphs. To cope with the resulting combinatorial explosion, an iterative beam search strategy is employed, dynamically maintaining a global pool of promising candidate root nodes, enabling effective control of diversification across iterations. To exploit the search for high-quality solutions, several known heuristics from the LCS literature are utilized into the standalone beam search procedure. To the best of our knowledge, this is the first comprehensive computational study on the VGLCS problem comprising 320 synthetic instances with up to 10 input sequences and up to 500 characters. Experimental results show robustness of the designed approach over the baseline beam search in comparable runtimes.
• Abstract（参考訳）: 本稿では、連続解の文字間のフレキシブルなギャップ制約を含む古典的LCS問題の一般化である可変Gapped Longest Common Subsequence (VGLCS)問題に対処する。 この問題は、残基間の構造的距離の制約を尊重しなければならない分子配列比較や、特定の時間的遅延の中でイベントが発生する必要のある時系列解析で生じる。 状態空間は一般に多数のルート状態部分グラフから構成されるルートベース状態グラフ表現に基づく探索フレームワークを提案する。 結果として生じる組合せ爆発に対処するため、反復ビーム探索戦略を採用し、期待されるルートノードのグローバルプールを動的に維持し、イテレーション間での多様化の効果的な制御を可能にする。 高品質な解を探すために,LCS文献からのいくつかの既知のヒューリスティックをスタンドアロンのビームサーチ手順に利用した。 我々の知る限りでは、最大10の入力シーケンスと最大500文字からなる320の合成インスタンスからなるVGLCS問題に関する、初めての総合的な計算研究である。 実験結果から, 対応するランタイムにおけるベースラインビーム探索に対する設計手法のロバスト性を示した。

関連論文リスト

• A Learning Search Algorithm for the Restricted Longest Common Subsequence Problem [40.64116457007417]
  RLCS問題(Restricted Longest Common Subsequence)はバイオインフォマティクスにおいて重要な応用である。 本稿では,将来性のある地域に向けて,探索プロセスを強化するための2つの新しいアプローチを提案する。 この論文の重要な貢献は、科学的な抽象が入力文字列として機能する実世界のインスタンスの生成である。
  論文  参考訳（メタデータ） (2024-10-15T20:02:15Z)
• Robust Detection of Lead-Lag Relationships in Lagged Multi-Factor Models [61.10851158749843]
  データ固有のリード-ラグ関係を発見することで、重要な洞察を得ることができる。 階層化多要素モデルにおけるリードラグ関係のロバスト検出のためのクラスタリング駆動手法を開発した。
  論文  参考訳（メタデータ） (2023-05-11T10:30:35Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。 標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。 我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。 本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
  論文  参考訳（メタデータ） (2023-04-01T15:50:18Z)
• Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection [9.175779296469194]
  本稿では動的プログラミングモデルの構造を利用して探索を高速化する新しい要素を提案する。 鍵となる考え方は、検索中にキャッシュされた拡張しきい値に問い合わせることによって、同じ動的プログラミング状態に対応するノードの繰り返し拡張を防止することである。 このキャッシング機構によって引き起こされるプルーニングは、アルゴリズムによって拡張されたノード数を著しく削減できることを示す実験である。
  論文  参考訳（メタデータ） (2022-11-22T10:18:33Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。 頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。 特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
  論文  参考訳（メタデータ） (2022-01-18T11:16:40Z)
• Determinantal Beam Search [75.84501052642361]
  ビームサーチは、ニューラルシーケンスモデルをデコードするためのゴーツー戦略である。 複数のソリューションを要求するユースケースでは、多様あるいは代表的なセットがしばしば望まれる。 ビームサーチを一連の部分決定問題として繰り返し行うことにより、アルゴリズムを多種多様なサブセット選択プロセスに変換することができる。
  論文  参考訳（メタデータ） (2021-06-14T13:01:46Z)

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

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