| Summary: | <p>Abstract</p> <p>Background:</p> <p>We present the <it>N</it>-map method, a pairwise and asymmetrical approach which allows us to compare sequences by taking into account evolutionary events that produce shuffled, reversed or repeated elements. Basically, the optimal <it>N</it>-map of a sequence <it>s </it>over a sequence <it>t </it>is the best way of partitioning the first sequence into <it>N </it>parts and placing them, possibly complementary reversed, over the second sequence in order to maximize the sum of their gapless alignment scores.</p> <p>Results:</p> <p>We introduce an algorithm computing an optimal <it>N</it>-map with time complexity <it>O </it>(|<it>s</it>| × |<it>t</it>| × <it>N</it>) using <it>O </it>(|<it>s</it>| × |<it>t</it>| × <it>N</it>) memory space. Among all the numbers of parts taken in a reasonable range, we select the value <it>N </it>for which the optimal <it>N</it>-map has the most significant score. To evaluate this significance, we study the empirical distributions of the scores of optimal <it>N</it>-maps and show that they can be approximated by normal distributions with a reasonable accuracy. We test the functionality of the approach over random sequences on which we apply artificial evolutionary events.</p> <p>Practical Application:</p> <p>The method is illustrated with four case studies of pairs of sequences involving non-standard evolutionary events.</p>
|
|---|