Beefy Boxes and Bandwidth Generously Provided by pair Networks DiBona
Welcome to the Monastery
 
PerlMonks  

string similarity by using a function sort_by_similarity()

by roopa (Initiate)
on Nov 08, 2009 at 08:46 UTC ( #805738=perlquestion: print w/ replies, xml ) Need Help??
roopa has asked for the wisdom of the Perl Monks concerning the following question:

hello, I am trying to compare string similarity based on the function sort_by_similarity().The strings are stored as array of hashes,I am unable to understand the way to get the sorted strings by similarity. I tried it in this way.
for($x=0;$x<$r;$x++){ @b = sort_by_similarity( \@querysubs,$inputsubs[$x]{'sequence'}); $y=\@b; #@array=@$y; #print $y->[0]; #$m=\@array; #print $m; $h=\($y->[0]); print $$h; #%hash=%\($y->[0]); foreach my $key(keys %hash){ #print "$key:$hash{$key}\n"; } }
Here $inputsubs$x{'sequence'} gives the input string and this is compared with the strings in @querysubs. Ex:-If the input string is
abcdef
It gets divided into abc bcd cde def according to 3 as the windowsize. If the query sequence is abcefg It even gets divided into abc bce cef efg

I need to compare each of the strings in the inputsubs with the querysubs and get the best matching string for each of these strings using the function sort_by_similarity(),but I am unable to understand the value returned by the function and unable to access the values and print them.

Please help me in solving out this problem.
Regards,
Roopa

20091109 Janitored by Corion: Added formatting, code tags, as per Writeup Formatting Tips

Comment on string similarity by using a function sort_by_similarity()
Select or Download Code
Re: string similarity by using a function sort_by_similarity()
by gmargo (Hermit) on Nov 08, 2009 at 10:33 UTC
Re: string similarity by using a function sort_by_similarity()
by shmem (Canon) on Nov 08, 2009 at 12:20 UTC
    Hello roopa,

    welcome to the monastery!
    Please read the nodes given by gmargo above.

    That said,

    I am trying to compare string similarity based on the function sort_by_similarity().

    It is next to impossible to help without a description (or better: code) of that subroutine. See I know what I mean. Why don't you?

    I need to compare each of the strings in the inputsubs with the querysubs and get the best matching string for each of these strings using the function sort_by_similarity(),but I am unable to understand the value returned by the function and unable to access the values and print them.

    I'm unable, too, since you provided no code. Anyways, thinking about the problem... here's how I would tackle it.

    In Perl you want to use sort to sort a collection. sort optionally takes a subroutine or block which will carry out the comparison of the items to be sorted. That evaluation must return -1, 0, or 1, for sort to determine their order in the collection that will be returned. Inside that block or function the two items to be compared magically appear in the variables $a and $b.

    Now, you want to sort a collection by similarity. Similarity is a relation between two elements. Sorting by that relation means: "are (a,b) more, less or equally similar to (a,c)?", i.e. sorting tuples by the amount of their similarity.

    To do that you need a way to measure that similarity between the elements of a tuple, then you can sort the tuples by the amount of similarity.

    use Math::Combinatorics qw( combine); my @collection; # list of strings my @tuples = combine( 2, @collection); my @similarity = sort { similarity($a) <=> similarity($b) } @tuples; sub similarity { my $tupel = shift; my $value; ... # determine similarity # between $tupel->[0] and $tupel->[1] # and store into $value ... return $value; }

    To avoid the maybe expensive evaluation of similarity() for each tuple at each comparison, it is convenient to determine those beforehand. i.e. using the Schwartzian Transform (see map):

    my @similarity = map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [ $_, similarity($_) ] } @tuples;

    Further optimization comprises populating @tuples with indices into @collection, which is left as an exercise to the reader.

      Hello gmargo, I would like to explain my problem in detail as follows. I would like to compare a biological DNA sequence say, Input sequence: GATCAAGAGCCACAATATAGATGGTCCCACCGCACCGCTGGGCGTGCCCCCGGGGATTGTAAACGGGTTCCTTGCAACCCGCTGTCCAGCCCAGCTGATGTTATGGAATCTTCTGGCTCCCCGTATCCCCTCCAGGGACATCCTGCAGTGCAGCCTGGGACCCAGGTTTACAGTTCACTCCCAGCTTCTGCTGTGAGAACCCAGGAACCGGCACCCTGGGGATGG Query sequence with which I am comparing say, CTGAGGGGTGGCTCTCTGAAGAGGTGGGTTGCCCGTGAGCTGTTTTTACTGTCCTTGTTTGCCACTTATAAGGACTGGTTCCCCCCACCCCCAAGAGCAGCACAGATTCATAGCACCTGCTGCCTCCACCGAGCATCCCCCCTGCTCTGGAAAATCCTCCCTGCATCTGCAGCCTCGTACGTGCCTGAAGTCATTTGGTACCTGGGCGAGACCTTGCGGGGGGCC based on certain windowsize and threshold.If windowsize is 5,the sequence gets partitioned into strings of length 5 as follows. Input sequence strings(@inputsubs):-GATCA ATCAA TCAAG CAAGA AAGCG.... Query sequence strings(@querysubs):-CTGAG TGAGG GAGGG AGGGG GGGGT.... Now each string in the @inputsubs is being compared with each and every string in the @querysubs.If there are atleast 3(or more than 3) same bases i.e., three similar characters,then they can be grouped into an array i.e., here 3 is the threshold. So,I want all those strings which can show the similarity >=threshold.When I have used brute force method to compare the strings,by using count method.It was taking more time.So I tried to use the function sort_by_similarity By using this function,I could get the array of strings which are sorted in an ascending order ie., starting from strings that have strings of lowest similarity and ending with the strings that have highest similarity with the querystrings.But I would like to have only those strings which have a similarity >=threshold i.e., If input is abcdef,query is abcefg windowsize is 3,threshold is 2,I would like to have Output:- abc bcd def My code is as follows. use String::Similarity::Group ':all'; #use Smart::Comments '###'; print "Enter the input sequence\n"; chomp($input=<STDIN>); print "Enter the query sequence\n"; chomp($query=<STDIN>); print "Windowsize\n"; $ws=<STDIN>; print "Threshold\n"; $ts=<STDIN>; $ilength=length $input; $qlength=length $query; #print $qlength; for($i=0;$i<=$ilength-$ws;$i++){ #print "in"; push(@inputsubs,substr($input,$i,$ws)); } $r=@inputsubs; for($j=0;$j<=$qlength-$ws;$j++){ push(@querysubs,substr($query,$j,$ws)); } $s=@querysubs; for($t=0;$t<$s;$t++){ @b=sort_by_similarity(\@inputsubs,$querysubs$t); } $v=@b; for($i=0;$i<$v;$i++){ print "$b$i\n"; my($closestname,$match)=similarest(\@b,$querysubs$i); if($match>=0.66){ #print "$closestname\n"; } } Please suggest me in case of any improvements or other less time taking methods to get the desired output. Regards, Roopa.
Re: string similarity by using a function sort_by_similarity()
by bobf (Monsignor) on Nov 08, 2009 at 15:26 UTC

    Based on your description I suspect that you are trying to compare DNA sequences, either at the level of a codon or translated to protein sequences. If that is the case, much more efficient and robust ways to do this are available. A more complete description of the problem would help.

    Recommended next steps:

    • Take a look at Bioperl
    • Post more information about the problem. Don't be afraid to use a little biology or bioinformatics terminology, which will help the bio monks around here get a better understanding of the problem.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://805738]
Approved by broomduster
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (7)
As of 2014-04-19 06:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (478 votes), past polls