5
$\begingroup$

We have two circular sequences, which means there is no start or end in the sequences, how to test if two sequence are equal or not in linear time? I have two circular sequences of E. Coli bacteria with length (4,639,221). I thought about attaching two sample of the first sequence and find the other one in it in linear time, but I was looking for a better idea, using a suffix tree is a suggestion that I think works for this problem.

$\endgroup$
  • 4
    $\begingroup$ What are your thoughts? $\endgroup$ – André Souza Lemos Dec 21 '16 at 20:18
  • 2
    $\begingroup$ @AndréSouzaLemos I thought we can choose a start and concatenate two string along each other and then find the second string in the first one, but I don't know if it's fine or not. $\endgroup$ – user137927 Dec 21 '16 at 21:04
  • 1
    $\begingroup$ Have you considered suffix trees? $\endgroup$ – Yuval Filmus Dec 21 '16 at 21:16
  • 2
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Dec 21 '16 at 22:40
  • 2
    $\begingroup$ Your own suggestion in the comments seems to work. If $y$ is shorter than $x$, then we find $y$ in a "rotation" of $x$ iff $y$ is a substring of $xx$. You mention you don't know whether that is fine. What is keeping you? $\endgroup$ – Hendrik Jan Dec 22 '16 at 23:54
4
$\begingroup$

Start with computing the lexicographlcally least circular substrings$^1$ of the both circular sequences and then compare them directly.

Alternatively you can check for the substring $A$ (the first seqience) in the string $BB$ (a concatenation of $B$, the second sequence) circular sequence with itself) using for example the KMP$^2$

You might also be interested in the application of the Suffix Trees (also Suffix Arrays) and this thesis reviewing the applications to DNA sequences.

$^{[1]}$(described in K. S. Booth. Lexicographically least circular substrings. Inf. Process. Lett., 10(4/5):240-242, 1980., and here
$^{[2]}$(Donald E. Knuth, James H. Morris, Jr., and Vaughan R. Pratt, SIAM J. Comput., 6(2), 323–350. Fast Pattern Matching in Strings

$\endgroup$
-2
$\begingroup$

Start in first list with a ptr with 1X speed and the second list with 2X speed. They meet at a point after some time if they both are the same lists. From then on, you can check if each of their nodes are the same. This is linear in time.

If they dont meet, they are not the same circular lists.

$\endgroup$
  • $\begingroup$ I think the question is not about checking if two given pointers are at the same circular lists but whether two separate lists are equal, meaning the elements are equal and in the same order. $\endgroup$ – Evil Dec 22 '16 at 3:58
  • $\begingroup$ Traverse till you get the same elements i.e. till they meet. $\endgroup$ – vidyasagarr7 Dec 22 '16 at 4:38
  • $\begingroup$ Traverse till you get the same elements i.e. till they meet. Then check if all the elements from then have the same value. This is what I was trying to say in the answer. $\endgroup$ – vidyasagarr7 Dec 22 '16 at 4:39
  • 1
    $\begingroup$ Ok. How do you know that the start is really the same point at the both lists? $\endgroup$ – Evil Dec 22 '16 at 4:51
  • 1
    $\begingroup$ I think this is a misunderstanding of the question. There's no reason to think that there is any node in common between the two sequences. Suppose the input is that one sequence is "ANABAN" and the other sequence is "BANANA". Those might be stored in completely disjoint locations in memory (so your procedure would say 'they are not the same circular lists'), but the desired answer is 'Yes the latter can be obtained by rotating the former'. $\endgroup$ – D.W. Dec 22 '16 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.