1

O（nm）で次の問題を解決する必要があります。n = | T | m = | P | ここで、T、P2つの文字列fはスコアリング関数です。

アルゴリズムは、score（P、T'）値が最大になるようにTのサブストリングT'を返す必要があります。

スコア（A、B）は、fに応じたアライメントAおよびBの最大値です。

fが離散的である場合（行列の対角線の重みが定数であるC以下であり、水平および垂直のエッジが0またはその他の定数であることを意味します）、モンジュ行列であるDIST行列から取得できることを私は知っています。ただし、この場合、fは（sigma * {-}）x（sigma * {-}）からR（'-'はギャップ）までの一般的な関数です。

何か案は？

4

1 に答える 1

0

アークが（i、j）→（i + 1、j）、（i + 1、j + 1）、（i、j + 1）であるグラフの最短経路を計算するアルゴリズムがいくつかあることに気づきました。 ）。このアルゴリズムの最も一般的な形式では、次の意味で、すべての弧の長さを個別に指定できます。

  • （i、j）→（i + 1、j）：Pの（i + 1）番目の文字をTのギャップに揃えるコスト
  • （i、j）→（i + 1、j + 1）：Pの（i + 1）番目の文字をTの（j + 1）番目の文字に揃えるコスト
  • （i、j）→（i、j + 1）：PのギャップをTの（j + 1）番目の文字に揃えるコスト

コストはマイナスになる可能性があります。サブストリングの問題を解決するには、すべての（i、j）→（i、j + 1）アークのコストをゼロにして、ペナルティなしでTから削除できるようにします。

于 2012-04-23T16:28:42.117 に答える