A Comparison of Three Heuristic Methods for Solving the Parsing Problem for Tandem Repeats

In many applications of tandem repeats the outcome depends critically on the choice of boundaries (beginning and end) of the repeated motif: for example, different choices of pattern boundaries can lead to different duplication history trees. However, the best choice of boundaries or parsing of the tandem repeat is often ambiguous, as the flanking regions before and after the tandem repeat often contain partial approximate copies of the motif, making it difficult to determine where the tandem repeat (and hence the motif) begins and ends. We define the parsing problem for tandem repeats to be the problem of discriminating among the possible choices of parsing.