Re: Finding Neighbours of a String

[inman]

I have used the Math::Combinatorics to work out the combinations and permutations needed. The aim is to work out all of the ways in which a string of a certain hamming distance could be created rather than create all the possible permutations of the string and test them.

use strict;
use warnings;
use Data::Dumper;
use Math::Combinatorics;

my $str = "TTTCGG";
my @str = split //, $str;
my $hammingDistance = 2;

# Calculate the total number of ways of getting the bases
my %bases;
my @baseopts = split //, 'ACGT' x $hammingDistance;
my $basecomb = Math::Combinatorics->new(count => $hammingDistance, dat
+a => [@baseopts], );
while(my @combo = $basecomb->next_combination){
    my $permu = Math::Combinatorics->new(data => [@combo], );
    while(my @permu = $permu->next_permutation){
        $bases{join '', @permu}++;
    }
}

# Make the list unique
my @baseperms;
push @baseperms, [split //, $_] foreach (keys %bases);


my %results;

my @n = (0 .. $#str);

# Calculate all the permutations of position that could give a change
# and work through the base combinations
my $poscomb = Math::Combinatorics->new(count => $hammingDistance, data
+ => [@n], );
while(my @combo = $poscomb->next_combination){
    foreach my $bases (@baseperms){
        my @newstr = @str;
        @newstr[@combo] = @$bases;
        $results{ join('', @newstr) }++;
    }
}

print "$_ ", hd($_, $str), "\n" foreach (sort keys %results);


sub hd {
    return ( $_[0] ^ $_[1] ) =~ tr/\001-\255//;
}