Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Re: how to count the no of repeats in a string (really!)

by lima1 (Curate)
on Nov 14, 2007 at 16:05 UTC ( #650783=note: print w/replies, xml ) Need Help??


in reply to how to count the no of repeats in a string (really!)

Sorry, couldn't resist :) : Once again a standard application of the nice data structure suffix trees/arrays. It is in general easier to explain this with suffix trees, but it also works quite analogous with arrays (which have several advantages). Take a look at the mississippi example in http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Suffix/. Now just enumerate all edge labels of nodes with more than one leaf: issi, i, ssi, si, p. These are all repeats because they are common prefixes of different suffixes of the string. There are algorithms that output only the maximal (overlapping) repeats issi and p.

Construction and calculation are both possible in linear time, but obviously with a lot of overhead (so the string must be quite large that this pays off - and then you don't want a Perl implementation).

And btw. it is not an "artificial problem". The human genome consists of many, many repeats (this is in fact the reason why the assembly is so hard) and we don't know much about most of them.

See also: http://en.wikipedia.org/wiki/Suffix_tree

  • Comment on Re: how to count the no of repeats in a string (really!)

Replies are listed 'Best First'.
Re^2: how to count the no of repeats in a string (really!)
by blazar (Canon) on Nov 14, 2007 at 16:17 UTC
    And btw. it is not an "artificial problem".

    I personally believe that I meant "not an actual problem of mine". Of course it may be an actual problem of someone else...

    Thank you for the supplied information. I'd still be interested in ways to do it with Perl. In fact it's true that the abstract algorithm could be implemented in any sufficiently powerful language. But some languages have syntactical features that make some taks particularly easy or difficult to implement... How can Perl specifically come to the rescue in this regard?

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (2)
As of 2021-04-15 04:14 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?