BioStar
Bioinformatician
Our Sponsors
Perl script to find edit distance between two sequences !
By BioStar 637 days ago
#!/usr/bin/perl
use strict;
use warnings;
sub edit_distance {
my ($s1, $s2) = @_;
my $len1 = length($s1);
my $len2 = length($s2);
my @dp;
for (my $i = 0; $i <= $len1; $i++) {
for (my $j = 0; $j <= $len2; $j++) {
$dp[$i][$j] = 0;
}
}
for (my $i = 0; $i <= $len1; $i++) {
$dp[$i][0] = $i;
}
for (my $j = 0; $j <= $len2; $j++) {
$dp[0][$j] = $j;
}
for (my $i = 1; $i <= $len1; $i++) {
for (my $j = 1; $j <= $len2; $j++) {
my $cost = substr($s1, $i-1, 1) eq substr($s2, $j-1, 1) ? 0 : 1;
$dp[$i][$j] = min($dp[$i-1][$j]+1, $dp[$i][$j-1]+1, $dp[$i-1][$j-1]+$cost);
}
}
return $dp[$len1][$len2];
}
sub min {
my $min = shift @_;
foreach (@_) {
$min = $_ if $_ < $min;
}
return $min;
}
# Example usage
my $seq1 = "ACGTAGCTAGCTGACTGAC";
my $seq2 = "CGTAGCTAGCTGACAGCTA";
my $distance = edit_distance($seq1, $seq2);
print "The edit distance between $seq1 and $seq2 is $distance.\n";
