Re: how to count the number 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.

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

Replies are listed 'Best First'.

Re^2: how to count the number 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?

[reply]


Just another Perl shrine
	PerlMonks