gpt4 book ai didi

algorithm - 我如何修改 Smith and Waterman perl 脚本以加快速度?

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:31:45 24 4
gpt4 key购买 nike

我找到了这个 perl 脚本,但是我有太多的序列需要分析。我想知道是否可以优化它?我在上面启动了 NYTProf,发现“计算匹配分数”、“计算差距分数”和“选择最佳分数”部分花费了大量时间。我必须修改数据结构吗?感谢您的帮助。

带引用的 perl 脚本:

    # Smith-Waterman  Algorithm
# from this website http://etutorials.org/Misc/blast/Part+II+Theory/Chapter+3.+Sequence+Alignment/3.2+Local+Alignment+Smith-Waterman/

# Smith-Waterman Algorithm

# usage statement
die "usage: $0 <sequence 1> <sequence 2>\n" unless @ARGV == 2;

# get sequences from command line
my ($seq1, $seq2) = @ARGV;

# scoring scheme
my $MATCH = 1; # +1 for letters that match
my $MISMATCH = -1; # -1 for letters that mismatch
my $GAP = -1; # -1 for any gap

# initialization
my @matrix;
$matrix[0][0]{score} = 0;
$matrix[0][0]{pointer} = "none";
for(my $j = 1; $j <= length($seq1); $j++) {
$matrix[0][$j]{score} = 0;
$matrix[0][$j]{pointer} = "none";
}
for (my $i = 1; $i <= length($seq2); $i++) {
$matrix[$i][0]{score} = 0;
$matrix[$i][0]{pointer} = "none";
}

# fill
my $max_i = 0;
my $max_j = 0;
my $max_score = 0;

for(my $i = 1; $i <= length($seq2); $i++) {
for(my $j = 1; $j <= length($seq1); $j++) {
my ($diagonal_score, $left_score, $up_score);

# calculate match score
my $letter1 = substr($seq1, $j-1, 1);
my $letter2 = substr($seq2, $i-1, 1);
if ($letter1 eq $letter2) {
$diagonal_score = $matrix[$i-1][$j-1]{score} + $MATCH;
}
else {
$diagonal_score = $matrix[$i-1][$j-1]{score} + $MISMATCH;
}

# calculate gap scores
$up_score = $matrix[$i-1][$j]{score} + $GAP;
$left_score = $matrix[$i][$j-1]{score} + $GAP;

if ($diagonal_score <= 0 and $up_score <= 0 and $left_score <= 0) {
$matrix[$i][$j]{score} = 0;
$matrix[$i][$j]{pointer} = "none";
next; # terminate this iteration of the loop
}

# choose best score
if ($diagonal_score >= $up_score) {
if ($diagonal_score >= $left_score) {
$matrix[$i][$j]{score} = $diagonal_score;
$matrix[$i][$j]{pointer} = "diagonal";
}
else {
$matrix[$i][$j]{score} = $left_score;
$matrix[$i][$j]{pointer} = "left";
}
} else {
if ($up_score >= $left_score) {
$matrix[$i][$j]{score} = $up_score;
$matrix[$i][$j]{pointer} = "up";
}
else {
$matrix[$i][$j]{score} = $left_score;
$matrix[$i][$j]{pointer} = "left";
}
}

# set maximum score
if ($matrix[$i][$j]{score} > $max_score) {
$max_i = $i;
$max_j = $j;
$max_score = $matrix[$i][$j]{score};
}
}
}

# trace-back

my $align1 = "";
my $align2 = "";

my $j = $max_j;
my $i = $max_i;

while (1) {
last if $matrix[$i][$j]{pointer} eq "none";

if ($matrix[$i][$j]{pointer} eq "diagonal") {
$align1 .= substr($seq1, $j-1, 1);
$align2 .= substr($seq2, $i-1, 1);
$i--; $j--;
}
elsif ($matrix[$i][$j]{pointer} eq "left") {
$align1 .= substr($seq1, $j-1, 1);
$align2 .= "-";
$j--;
}
elsif ($matrix[$i][$j]{pointer} eq "up") {
$align1 .= "-";
$align2 .= substr($seq2, $i-1, 1);
$i--;
}
}

$align1 = reverse $align1;
$align2 = reverse $align2;
print "$align1\n";
print "$align2\n";

最佳答案

你可以尽量避免一遍又一遍地做同样的事情。

  1. 您可以尝试在循环之前将序列拆分为字符一次,而不是通过索引使用最有可能更快的访问,而不是从您的序列中删除单个字符。

    例子:

    my $string = "Hello, how are you?";
    my @chars = split //, $string; # Or: unpack 'a*', $string
    print "Eighth char: $chars[7]\n";
  2. my $letter2 = substr($seq2, $i-1, 1); 可以进入外循环,因为 j 在内循环中永远不会改变循环。

    for(my $i = 1; $i <= length($seq2); $i++) {
    my $letter2 = substr($seq2, $i-1, 1);
    for(my $j = 1; $j <= length($seq1); $j++) {
  3. 避免较慢且复杂的 C 风格循环。

    for my $i (1..length($seq2)) {
    my $letter2 = substr($seq2, $i-1, 1);
    for my $j (1..length($seq1)) {
  4. pointer 的值不是字符串,而是整数。您可以使用常量来保持它的可读性。

    use constant {
    POINTER_NONE => 0,
    POINTER_LEFT => 1,
    ...
    };
  5. 预先计算$j-1$i-1也可能带来一点小优势。

注意您应该在每次更改前后分析您的代码以查看速度是否提高。

所有这些都是微小的改进。真正的问题是你有一个二次算法。

关于algorithm - 我如何修改 Smith and Waterman perl 脚本以加快速度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47754639/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com