Needleman 希望算法 (perl)

Question

所以我的问题是尝试实现 Needleman Wunsch 算法以及垂直和水平的间隙分数运行内存不足并且无法正确实现。这可能是内存中的一个简单循环错误计算，但对于我来说，我无法看到它。这是代码：

$seq1 = "ACTTCAATCGGT";
$seq2 = "ACTGGTCAATCGGT";
$len1 = length($seq1);
$len2 = length($seq2);

上面的序列。

@matrix = ();
my $gapscore = -1;

my $matchscore = 1;
my $mismatchscore = 0;
$matrix[0][0] = 0;

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

$gapscore = -1; 

for ($j = 1; $j < $len2; $j++) {
     $matrix[0][$j] = $gapscore;         
     $gapscore--;

}

$gapscore = -1;

所以上面的代码正确地实现了 0...n 和 0...n 水平和垂直方向的矩阵点。下一个代码尝试通过填充矩阵中的其余值来实现矩阵。

for($x = 1; $x < $len2; $x++) { # going through sequence1
   for($y = 1; $y < $len1; $y++) { # going through sequence2

        my ($diagonal, $horizontal, $vertical); 

        my $Firstletter = substr($seq1,$x-1,1);
        my $Secondletter = substr($seq2,$y-1,1); 


        # gap scores:
        $vertical = $matrix[$x-1][$y] + $gapscore;
        $horizontal = $matrix[$x][$y-1] + $gapscore;

        # matching scores on diagonal:
        if($Firstletter eq $Secondletter) {
             $diagonal = $matrix[$x-1][$y-1] + $matchscore;
        }
        else {
             $diagonal = $matrix[$x-1][$y-1] + $mismatchscore;
        } 
    }
}

垂直和水平变量导致内存问题。我不确定为什么。如果有人能提供一些见解，我将不胜感激！

Answer 1

for($x = 1; $x < $len2; $x++) { # going through sequence1
   for($y = 1; $y < $len1; $y++) { # going through sequence2

错误，如所写，第一个循环经过 sequence2，第二个循环经过 sequence1。

看来您已经倒排了索引。这可能会导致索引超出范围错误，并且在某些情况下还会导致执行时间变慢。

可能的修复：交换上面代码中的 len2 和 len1。

Answer 2

我不明白你为什么运行内存不足，但你有一些差一的错误。该矩阵的列比序列 1 中的碱基多一列，比序列 2 中的碱基多一行。这意味着您的索引应该运行从 0 到 $len1 和 0 到 $len2，但你正在停止一个短片。

这应该对您有所帮助。它正确地构建了数组，但我还没有写下一个步骤，即跟踪通过对角线的最佳路径。

use strict;
use warnings;

use List::Util 'max';

STDOUT->autoflush;

my ($seq1, $seq2) = qw/ ACTTCAATCGGT ACTGGTCAATCGGT /;
my ($len1, $len2) = map length, $seq1, $seq2;
my @seq1 = $seq1 =~ /./g;
my @seq2 = $seq2 =~ /./g;

my @matrix;
$matrix[$_][0] = -$_ for 0 .. $len2;
$matrix[0][$_] = -$_ for 0 .. $len1;

for my $x ( 1 .. $len2 ) {     # Rows (bases of sequence 2)
    for my $y ( 1 .. $len1 ) { # Columns (bases of sequence 1)

        my $match = $seq1[$y-1] eq $seq2[$x-1];

        my @scores = (
          $matrix[$x-1][$y] - 1,  # Up
          $matrix[$x][$y-1] - 1,  # Left
          $match ? $matrix[$x-1][$y-1] + 1 : $matrix[$x-1][$y-1] - 1, # Diagonal
        );

        $matrix[$x][$y] = max @scores;
    }        
}

for my $i ( 0 .. $len2 ) {
    my $row = $matrix[$i];
    print join(' ', map { sprintf '%3d', $_ } @$row), "\n";
}

输出

  0  -1  -2  -3  -4  -5  -6  -7  -8  -9 -10 -11 -12
 -1   1   0  -1  -2  -3  -4  -5  -6  -7  -8  -9 -10
 -2   0   2   1   0  -1  -2  -3  -4  -5  -6  -7  -8
 -3  -1   1   3   2   1   0  -1  -2  -3  -4  -5  -6
 -4  -2   0   2   2   1   0  -1  -2  -3  -2  -3  -4
 -5  -3  -1   1   1   1   0  -1  -2  -3  -2  -1  -2
 -6  -4  -2   0   2   1   0  -1   0  -1  -2  -2   0
 -7  -5  -3  -1   1   3   2   1   0   1   0  -1  -1
 -8  -6  -4  -2   0   2   4   3   2   1   0  -1  -2
 -9  -7  -5  -3  -1   1   3   5   4   3   2   1   0
-10  -8  -6  -4  -2   0   2   4   6   5   4   3   2
-11  -9  -7  -5  -3  -1   1   3   5   7   6   5   4
-12 -10  -8  -6  -4  -2   0   2   4   6   8   7   6
-13 -11  -9  -7  -5  -3  -1   1   3   5   7   9   8
-14 -12 -10  -8  -6  -4  -2   0   2   4   6   8  10

Needleman 希望算法 (perl)

Needleman Wunsch Algorithm (perl)

algorithm

perl

matrix