最も近い文字列

理論計算機科学において、最も近い文字列はNP困難な計算問題であり、^[1]入力文字列の集合の幾何学的中心を見つけようとするものである。

「中心」という言葉を理解するには、2つの文字列間の距離を定義する必要があります。通常、この問題はハミング距離を念頭に置いて研究されます。

正式な定義

より正式には、長さmのn個の文字列s ₁、s ₂、 ...、s _nが与えられたとき、最近接文字列問題は、すべてのiに対してd ( s、si ) ≤ kとなるような長さmの新しい文字列sを探す_問題です。ここで、dはハミング距離、kは可能な限り小さい値です。^[2]最近接文字列問題の決定問題バージョンは NP 完全であり、代わりにk を別の入力として受け取り、すべての入力文字列のハミング距離k以内の文字列があるかどうかを尋ねます。 ^[1]

最近接文字列問題は、要素間の距離がハミング距離を使用して測定される一般的な1 中心問題の特殊なケースとして考えることができます。

モチベーション

バイオインフォマティクスにおいて、最近接文字列問題は、 DNA内の信号を見つける問題の中で集中的に研究されている側面です。

簡素化とデータ削減

最も近い文字列のインスタンスには、問題に本質的ではない情報が含まれている場合があります。ある意味では、最も近い文字列の通常の入力には、問題の難しさには寄与しない情報が含まれています。例えば、一部の文字列に文字aが含まれており、文字zが含まれていない場合、すべての a を z に置き換えると、本質的に同等のインスタンスが生成されます。つまり、変更されたインスタンスの解から元の解を復元でき、その逆も同様です。

入力の正規化

同じ長さを持つすべての入力文字列を重ね書きすると、行列が形成されます。特定の行タイプは、解に対して本質的に同じ意味を持ちます。例えば、ある列のエントリ（a、a、b）を別の列（x、x、y）に置き換えると、異なる解の文字列が得られる可能性がありますが、どちらの列も同じ構造、つまり最初の2つのエントリは同じですが、3番目のエントリとは異なるため、解の可能性には影響しません。

入力インスタンスは、各列において最も頻繁に出現する文字をaに、2番目に頻繁に出現する文字をbに置き換えるなどして正規化できます。正規化されたインスタンスの解が与えられれば、各列において解の文字を元のインスタンスに再マッピングすることで、元のインスタンスを見つけることができます。

列の順序は問題の難しさには影響しません。つまり、すべての入力文字列を特定の順列 π に従って並べ替え、その変更されたインスタンスに対する解文字列sを得た場合、 π ⁻¹ ( s ) は元のインスタンスに対する解になります。

例

3つの入力文字列uvwx、xuwv、xvwuを持つインスタンスがあるとします。これは次のような行列として表すことができます。

あなた	v	わ	×
×	あなた	わ	v
×	v	わ	あなた

最初の列の値は ( u , x , x ) です。xは最も頻繁に出現する文字なので、これをaに置き換え、次に出現頻度の高い文字であるu をbに置き換えて、新しい最初の列 ( b , a , a ) を取得します。2番目の列の値は ( v , u , v ) です。最初の列と同様に、vをaに、uをbに置き換えて、新しい2番目の列 ( a , b , a ) を取得します。すべての列に対して同じことを行うと、正規化されたインスタンスが得られます。

b	1つの	1つの	1つの
1つの	b	1つの	b
1つの	1つの	1つの	c

正規化から得られるデータ削減

入力を正規化すると、アルファベットのサイズが最大で入力文字列の数まで削減されます。これは、実行時間がアルファベットのサイズに依存するアルゴリズムに役立ちます。

近似可能性

Liらは多項式時間近似方式^[3]を開発しましたが、これは隠れた定数が大きいため実際には使用できませんでした。

固定パラメータの扱いやすさ

Closest Stringは、kが入力文字列の数、Lがすべての文字列の長さ、dが解文字列から任意の入力文字列までの望ましい最大距離である場合に、次のように解くことができます。^[4] $O(kL+kd\cdot d^{d})$

他の問題との関係

最近接文字列問題は、より一般的な最近接部分文字列問題の特殊なケースであり、厳密にはより困難です。最近接文字列問題はいくつかの点で固定パラメータに対して扱いやすいことが分かっていますが、最近接部分文字列問題はこれらのパラメータに関して W[1]困難です。

参考文献

^ ab Lanctot, J. Kevin; Li, Ming; Ma, Bin; Wang, Shaojiu; Zhang, Louxin (2003)、「文字列選択問題の識別」、Information and Computation、185 (1): 41– 55、doi :10.1016/S0890-5401(03)00057-9、MR 1994748
^ Bin Ma; Xiaming Sun (2008). 「最近接文字列および部分文字列問題に対するより効率的なアルゴリズム」(PDF) .計算分子生物学研究. 第12回計算分子生物学研究国際会議 (RECOMB). LNCS . Vol. 4955. Springer. pp. 396– 409. doi :10.1007/978-3-540-78839-3_33. ISBN 978-3-540-78838-6。
^ M. Li; B. Ma; L. Wang. (2002)、「最近接文字列と部分文字列の問題について」(PDF)、Journal of the ACM、49 (2): 157– 171、arXiv : cs/0002012、doi :10.1145/506147.506150、S2CID 965332
^ イェンス・グラム;ロルフ・ニーダーマイヤー; Peter Rossmanith (2003)、「最近接文字列および関連問題の固定パラメータアルゴリズム」、Algorithmica、37 : 25–42、CiteSeerX 10.1.1.61.736、doi :10.1007/s00453-003-1028-3、S2CID 8206021

[llmwz-1] Lanctot, J. Kevin; Li, Ming; Ma, Bin; Wang, Shaojiu; Zhang, Louxin (2003)、「文字列選択問題の識別」、Information and Computation、185 (1): 41– 55、doi :10.1016/S0890-5401(03)00057-9、MR 1994748

[2] Bin Ma; Xiaming Sun (2008). 「最近接文字列および部分文字列問題に対するより効率的なアルゴリズム」(PDF) .計算分子生物学研究. 第12回計算分子生物学研究国際会議 (RECOMB). LNCS . Vol. 4955. Springer. pp. 396– 409. doi :10.1007/978-3-540-78839-3_33. ISBN 978-3-540-78838-6。

[3] M. Li; B. Ma; L. Wang. (2002)、「最近接文字列と部分文字列の問題について」(PDF)、Journal of the ACM、49 (2): 157– 171、arXiv : cs/0002012、doi :10.1145/506147.506150、S2CID 965332

[4] イェンス・グラム;ロルフ・ニーダーマイヤー; Peter Rossmanith (2003)、「最近接文字列および関連問題の固定パラメータアルゴリズム」、Algorithmica、37 : 25–42、CiteSeerX 10.1.1.61.736、doi :10.1007/s00453-003-1028-3、S2CID 8206021