1

このコードについて少し助けが必要です。私は再帰的であるべきセクションを知っています、または少なくとも私はそう思うと思いますが、それを実装する方法がわかりません。ゼロ値に戻る複数のルートを見つけるアライメントマトリックスからパスファインディングプログラムを実装しようとしています。たとえば、私のコードを実行し、最初のシーケンスとしてCGCAを挿入し、2番目のシーケンスとしてCACGTATを挿入し、一致、不一致、およびギャップのスコアとして1、0、および-1を挿入したとします。プログラムは、HDHHDDとしてのパスと、

CACGTAT

CGC--A-。

しかし、私がいくつあるかわからないことを除いて、これよりも多くの可能なパスとアラインメントがあります。私がやりたいのは、コードの一部をループバックさせて、他のパスとアラインメントを見つけ、最初と同じコードを使用して、可能なアラインメントがなくなるまでです。これを行うためにネット上で見つけた最善の方法は、再帰です。ただし、誰もそれを行う方法を説明できません。この場合、さらに2つのパスとアラインメントHDDDHHDとCACGTAT、およびC--GCA-とが必要です。HDDDDHH、CACGTATおよび--CGCA-。このタスクを実行するためのコーディング方法がわかりません。

# Implementation of Needleman and Wunsch Algorithm

my($seq1, $len1, $seq2, $len2, $data, @matrix, $i, $j, $x, $y, $val1, $val2);
my($val3, $pathrow, $pathcol, $seq1loc, $seq2loc, $gapscore, $matchscore, $mismatchscore);

#first obtain the data from the user. 
print "Please enter the first sequence for comaprsion\n";
$seq1=<STDIN>;
chomp $seq1;

print "Please enter the second sequence for comparsion\n";
$seq2=<STDIN>;
chomp $seq2;


# adding extra characters so sequences align with matrix
# saves some calculations later on
$seq1 = " " . $seq1;
$seq2 = " " . $seq2;
$len1 = length($seq1);
$len2 = length($seq2);

print "Enter the match score: ";
$matchscore=<STDIN>;
chomp $matchscore;

print "Enter the mismatch score: ";
$mismatchscore=<STDIN>;
chomp $mismatchscore;

print "Enter the gap score: ";
$gapscore=<STDIN>;
chomp $gapscore;

# declare a two dimensional array and initialize to spaces
# array must contain one extra row and one extra column
@matrix = ();  
for($i = 0; $i < $len1; $i++){  
   for($j = 0; $j < $len2; $j++){  
      $matrix[$i][$j] = ' ';  
   }  
}  

# initialize 1st row and 1st column of matrix  
$matrix[0][0] = 0;  
for ($i = 1; $i < $len1; $i ++){  
    $matrix[$i][0] = $matrix[$i-1][0] + $gapscore;  
}  
for ($i = 1; $i < $len2; $i ++){  
    $matrix[0][$i] = $matrix[0][$i-1] + $gapscore;  
}  


# STEP 1:
# Fill in rest of matrix using the following rules:
# determine three possible values for matrix[x][y]
# value 1 = add gap score to matrix[x][y-1]
# value 2 = add gap score to matrix[x-1][y]
# value 3 = add match score or mismatch score to 
#           matrix[x-1][y-1] depending on nucleotide 
#           match for position x of $seq1 and position y
#           of seq2
# place the largest of the three values in matrix[x][y]
#
# Best alignment score appears in matrix[$len1][$len2].

for($x = 1; $x < $len1; $x++){  
   for($y = 1; $y < $len2; $y++){  
 $val1 = $matrix[$x][$y-1] + $gapscore;  
 $val2 = $matrix[$x-1][$y] + $gapscore;  
 if (substr($seq1, $x, 1) eq substr($seq2, $y, 1)){  
           $val3 = $matrix[$x-1][$y-1] + $matchscore;  
 }  
 else{  
    $val3 = $matrix[$x-1][$y-1] + $mismatchscore;  
 }  
 if (($val1 >= $val2) && ($val1 >= $val3)){  
    $matrix[$x][$y] = $val1;  
 }  
 elsif (($val2 >= $val1) && ($val2 >= $val3)){  
    $matrix[$x][$y] = $val2;  
 }  
 else{  
    $matrix[$x][$y] = $val3;  
 }  
   }  
}  

# Display scoring matrix  
print "MATRIX:\n";   
for($x = 0; $x < $len1; $x++){  
   for($y = 0; $y < $len2; $y++){  
 print "$matrix[$x][$y] ";  
   }  
   print "\n";  
}  
print "\n";    

# STEP 2:  
# Begin at matrix[$len1][$len2] and find a path to   
# matrix[0][0].  
# Build string to hold path pattern by concatenating either   
# 'H' (current cell produced by cell horizontally to left),   
# 'D' (current cell produced by cell on diagonal),   
# 'V' (current cell produced by cell vertically above)
# ***This is were I need help I need this code to be recursive, so I can find more then one path***

$pathrow = $len1-1;  
$pathcol = $len2-1;  

while (($pathrow != 0) || ($pathcol != 0)){  
    if ($pathrow == 0){  
       # must be from cell to left  
       $path = $path . 'H';  
       $pathcol = $pathcol - 1;  
    }  
    elsif ($pathcol == 0){  
       # must be from cell above  
       $path = $path . 'V';  
       $pathrow = $pathrow - 1;  
    }  
    # could be from any direction  
    elsif  (($matrix[$pathrow][$pathcol-1] + $gapscore) == $matrix[$pathrow][$pathcol]){  
       # from left  
       $path = $path . 'H';  
       $pathcol = $pathcol - 1;  
    }  
    elsif (($matrix[$pathrow-1][$pathcol] + $gapscore) == $matrix[$pathrow][$pathcol]){  
       # from above  
       $path = $path . 'V';  
       $pathrow = $pathrow - 1;  
    }   
    else{  
       # must be from diagonal  
       $path = $path . 'D';  
       $pathrow = $pathrow - 1;  
       $pathcol = $pathcol - 1;  
    }  


}   



print "Path is $path\n";   

# STEP 3:
# Determine alignment pattern by reading path string 
# created in step 2.
# Create two string variables ($alignseq1 and $alignseq2) to hold 
# the sequences for alignment.
# Reading backwards from $seq1, $seq2 and path string, 
#   if string character is 'D', then 
#      concatenate to front of $alignseq1, last char in $seq1 
#      and to the front of $alignseq2, last char in $seq2
#   if string character is 'V', then 
#      concatenate to front of $alignseq1, last char in $seq1 
#      and to the front of $alignseq2, the gap char
#   if string character is 'H', then 
#      concatenate to front of $alignseq1 the gap char
#      and to the front of $alignseq2, last char in $seq2
# Continue process until path string has been traversed.
# Result appears in string $alignseq1 and $seq2
***#I need this code to be recursive as well.***

$seq1loc = $len1-1;  
$seq2loc = $len2-1;  
$pathloc = 0;  
print length($path);  
while ($pathloc < length($path)){  
   if (substr($path, $pathloc, 1) eq 'D'){  
      $alignseq1 = substr($seq1, $seq1loc, 1) . $alignseq1;  
      $alignseq2 = substr($seq2, $seq2loc, 1) . $alignseq2;  
      $seq1loc--;  
      $seq2loc--;  
   }  
   elsif (substr($path, $pathloc, 1) eq 'V'){  
      $alignseq1 = substr($seq1, $seq1loc, 1) . $alignseq1;  
      $alignseq2 = '-' . $alignseq2;  
      $seq1loc--;  
   }    
   else{  # must be an H  
      $alignseq1 = '-' . $alignseq1;  
      $alignseq2 = substr($seq2, $seq2loc, 1) . $alignseq2;  
      $seq2loc--;  
   }    
   $pathloc++;  
}  

print "\nAligned Sequences:\n";  
print "$alignseq2 \n";  
print "$alignseq1 \n";  

# statement may be needed to hold output screen  
print "Press any key to exit program";  
$x = <STDIN>;   

誰かが疑問に思っているなら、これはニードルマン-ブンシュアルゴリズムです。ここでのどんな助けも大いに認められるでしょう。

4

3 に答える 3

7

あなたが何をしようとしているのか正確に理解していないので、私は答えを提供することはできませんが、私はいくつかの一般的なアドバイスを提供することができます。

狭く定義されたタスクを実行する個別のサブルーチンにコードを編成し始めます。さらに、中央アルゴリズムを実装するサブルーチンは、キーボードからの入力を受け取り、画面に出力を生成することを目的としてはなりません。むしろ、引数として入力を受け取り、結果を返す必要があります。ユーザー入力または画面出力が必要な場合、これらのタスクは、主要なアルゴリズムと混同するのではなく、別々のサブルーチンに含める必要があります。

そのパスをたどる最初の(そして部分的な)ステップは、プログラム全体を取得し、それをサブルーチン定義で囲み、必要な引数を使用してサブルーチンを呼び出すことです。キーの結果を出力する代わりに、サブルーチンはそれらを返す必要があります。具体的には、、、@matrixの値とともにへ$pathの参照$alignseq1です$alignseq2

sub NW_algo {
    my ($seq1, $seq2, $matchscore, $mismatchscore, $gapscore) = @_;

    # The rest of your code here, but with all print
    # statements and <STDIN> inputs commented out.

    return \@matrix, $path, $alignseq1, $alignseq2;
}

my(@return_values) = NW_algo('CGCA', 'CACGTAT', 1, 0, -1);

Print_matrix($return_values[0]);

sub Print_matrix {
    for my $m ( @{$_[0]} ){
        print join(' ', @$m), "\n";
    }
}

この時点で、他のコードから呼び出すことができるアルゴリズムが用意されているため、今後のプログラムのテストとデバッグが容易になります。たとえば、入力データのさまざまなセットを定義NW_algo()し、各セットで実行できます。そうして初めて、再帰やその他の手法について考えることができます。

于 2009-09-18T14:32:09.133 に答える
5

Needleman-Wunsch は動的計画法アルゴリズムであるため、ほとんどの作業は DP 行列を計算するまでに完了しています。DPマトリックスを取得したら、マトリックスをバックトラックして最適な配置を見つける必要があります。問題は、斜めに移動できることを除いて、タクシーのジオメトリに少し似ています。基本的に、行列をバックトラックする必要がある場合、上、左、または斜めのいずれかを選択する代わりに、3 つの再帰呼び出しを行うことで 3 つすべてを実行し、それぞれが上、左、または斜めのそれぞれに対して自分自身を呼び出します。あなたはあなたの出発点に到達します。再帰の各ストランドによってトレースされるパスは、各アライメントを引き出します。

編集: したがって、基本的には、ステップ 2 をサブプロシージャ (位置を取得し、これまでにトレースされたパス) に配置する必要があるため、それ自体を何度も呼び出すことができます。もちろん、プロシージャを定義した後は、トレース プロセスを実際に開始するために 1 回呼び出す必要があります。

sub tracePaths {
    $x = shift;
    $y = shift;
    $pathSoFar = shift; # assuming you're storing your path as a string
    #
    # ... do some work ...
    #
    tracePaths($x - 1, $y, $pathSoFar . something);
    tracePaths($x, $y - 1, $pathSoFar . somethingelse);
    tracePaths($x - 1, $y - 1, $pathSoFar . somethingelselse);
    #
    #
    #
    if(reached the end) return $pathSoFar;
}
# launch the recursion
tracePaths(beginningx, beginningy, "");
于 2009-09-18T14:42:08.023 に答える
4

これはあなたの問題について具体的に述べているわけではありませんが、本Higher Order Perlをチェックする必要があるかもしれません。多くの高度な手法 (再帰など) の使用方法について説明します。

于 2009-09-18T17:59:14.650 に答える