Longest DNA sequence that appears at least twice (only one DNA string as input)

My question is to find the longest DNA sub-sequence that appears at least twice. The input is only one DNA string, NOT TWO strings as other LCS programs.

I have done my 4th program and it seems to be working and efficient (computes 10k strings in 4 seconds). But I don't know if this is 100 % correct. This is a really important project for me and I have really tried to make it.

Kindly provide your suggestions regarding my logic and program implementation in Java (I don't know advanced program techniques involving stacks, queues and linked lists in Java).

Logic:

1. Enter string;
2. Make new strings from the original string - start from beginning-- at each step increasing by one letter;
3. Put these strings in an array;
4. Sort the array in alphabetical order;
5. Compare the prefixes between each string in the sorted array --looking for similar substrings ;
6. Print the longest one(s).

import java.util.*;

/**
*
* @author Pavin
*/
public class dna3 {

public static String check(String a,String b)
{
String f="";
if (a.length()<b.length())
{
String h="";
//  String f ="";
int r=a.length();
int t=b.length();

// }
String c="";
//   String f ="";
if ((a==null)||(b==null))
{
c="";
}
else
{
for (int i=0;i<a.length();i++)
{
//for (int j=0;j<b.length();j++)
{
char d=a.charAt(i);
char e=b.charAt(i);
if (d==e)
{
c=String.valueOf(e);
f=f+c;

}
if (d!=e)
{
break;

}
}
}
}
}
if (a.length()>b.length())
{
String h="";
//  String f ="";
int r=a.length();
int t=b.length();

// }
String c="";
//   String f ="";
if ((a==null)||(b==null))
{
c="";
}
else
{
for (int i=0;i<b.length();i++)
{
//for (int j=0;j<b.length();j++)
{
char d=a.charAt(i);
char e=b.charAt(i);
if (d==e)
{
c=String.valueOf(e);
f=f+c;

}
if (d!=e)
{
break;

}
}
}
}

}
return f;
}

/**
* @param args the command line arguments
*/
public static void main(String[] args) {

Scanner sc=new Scanner(System.in);
System.out.println("Enter DNA string");

String a=sc.nextLine();
String c;
String d;
int b=a.length();
String arr[]=new String [b+1];
int i;

for (i=0;i<b;i++)
{
c=a.substring(i,b);
arr[i]=c;

}
/*    System.out.println("Before sort>>> ");
for (i=0;i<b;i++)
{

System.out.println(arr[i]);

}*/
String temp;
for(int x=1;x<b;x++)
{
for(int y=0;y<b-x;y++)
{
if(arr[y].compareTo(arr[y+1])>0)
{
temp=arr[y];
arr[y]=arr[y+1];
arr[y+1]=temp;

}
}
}

/*  System.out.println("After sort>>> ");

for(i=0;i<b;i++){
System.out.println(arr[i]);
}   */

System.out.println("Longest substring with frequency equal to two or more >>> ");

String v1;
String v2;
String v3;

// dnabxcfnabionabxuinab
int w=1;
for (i=0;i<b-1;i++)
{
v1= arr[i];
v2=arr[i+1];
v3=check(v1,v2);
int q=v3.length();

if (q>=w)
{
w=q;

}
}
String v4="";
for (i=0;i<b-1;i++)
{
v1= arr[i];
v2=arr[i+1];
v3=check(v1,v2);
int s=v3.length();

if ((s==w)&&(v4.compareTo(v3)!=0))
{
v4=v3;

System.out.println(v3);
}
}

// TODO code application logic here
}
}
• What is the expected bahaviour with overlaps... i.e. is the longest sequence in this string ababa the value aba or just ab or ba ? Nov 20 '13 at 20:19
• The answer to "ababa" should be "aba". With Overlaps, yes.
– user32400
Nov 20 '13 at 20:31
• When providing sequence "abcd", the array of substrings does not include some of the valid combinations. Excluded values include "abc" and "bc". Single loop is not sufficient to extract all the data. Nov 20 '13 at 21:46
• @Origineil I thought so as well, at first, but the 'second' loop is actually inside the check() method... I believe it does actually work Nov 20 '13 at 22:59
• Is it just me, or does this look like it's either NP-hard or wrong? You're essentially matching the regex (.+).*\1, so if you could do it in P time, you could also solve regex with back-references in P time, which is known to be NP-hard. Honestly, I can't read this code, please use real variable names, so I can't really analyze its complexity, but if it runs in polynomial time, and the problems are equivalent, there's some input for which it will fail. Nov 23 '13 at 20:56

There are a number of items which concern me in your code.

First up, when I pull your code in to eclipse, it immediately gives me lots of warnings.... which are easy to fix, but make the code cumbersome. Also there's a couple of other items:

1. Scanner sc .... is not closed (always close IO streams when you are done with them).
2. Many variables are not used: in main() there's d, and in check() there's h, r, and t (which are unused both places they occur - both in the 'if' side and 'else' side of the condition).
3. The remaining variable names are not very reader-friendly... apart from sc for 'scanner', arr, and temp, all the other variables are single-letter: a, b, d, h, i, j, q, w, x, and y. Oh, there is also v0, v1, v2, v3, and v4. This all makes it very hard to read/understand your code.
4. While it's a personal preference, the official Java code-style guide recommends putting the open brace { on the same line as the block introduction, not on the following line. For example:
if (...) {
is all on one line.

Going through things in order of execution....

The Scanner should be closed. The best way to do this is (in Java7) to use a 'try-with-resource' structure:

try (Scanner scanner = new Scanner(System.in)) {
.... all your code goes in here ....
}

Next up, why is the arr size b + 1 and not b ? It should be:

String[] arr = new String[b];

You have a few blocks of code which are unnecessarily complicated. For example:

for (i=0;i<b;i++)
{
c=a.substring(i,b);
arr[i]=c;

}

This has a few problems:

1. unless you have a good reason, when you use a loop like this, do not declare the loop variable outside the loop (in this case, the i). It makes things confusing.
2. Using b in the substring leads to confusion. b is the full string length, and it implies that you are going to get more characters than there actually are. In this case, the substring method silently ignores your request for too many characters. You should do this explicitly by using a.substring(i) instead of a.substring(i, b)
3. the c variable is completely unnecessary - use arr[i] = a.substring(i);

The code should look like:

for (int i = 0; i < a.length(); i++) {
arr[i] = a.substring(i);
}

The following block is also unnecessary:

String temp;
for(int x=1;x<b;x++)
{
for(int y=0;y<b-x;y++)
{
if(arr[y].compareTo(arr[y+1])>0)
{
temp=arr[y];
arr[y]=arr[y+1];
arr[y+1]=temp;

}
}
}

This is a sort, so sort it! Use the Collections API:

Arrays.sort(arr);

Now, I am not sure why the code splits at this point in to the two sections.... but, when I looked in to the check() method, the first thing that I noticed was that if a and b are both the same length, it immediately returns a 'no-match' even if they may be the same. (never mind, no two strings will have the same length). Instead of if (a.length() > b.length()) ... and if (b.length() > a.length()) you should simply use an if (....) {....} else {....}

There are other problems I am sure, but that's enough for the moment.

The next item I would criticize is the code duplication in the check() method. There is no need to have the length-checks in that method. Consider renaming the check method to have:

public static String check(String big, String small) {...}

and then, outside the method, you do:

// check the values, using the longest one first....
String v3= v1.length() > v2.length() ? check(v1,v2) : check(v2, v1);

Finally, inside the check method, you should not need to check for null values in the input, because you should not have added nulls when initializing the arr array. This strips a bit of code out.

Also, the String concatenation f = f + c line is 'bad form'. You should, instead, simply be able to do something like:

if (d!=e) {
return small.substring(0, i - 1);
}
}
• Instead of using Collections.sort(Arrays.asList(arr));, there is also Arrays.sort. Nov 20 '13 at 22:23
• And THANK YOU for mentioning the variable names, that was the first I could think of. You'll get an upvote as soon as I have some ammo again. Nov 20 '13 at 22:24
• @SimonAndréForsberg - of course, Arrays.sort(...) ... I was temporarily muddled by another problem I have seen recently where I wanted Arrays.shuffle(...) and that does not exist! Nov 20 '13 at 22:56
• Thank You for the suggestions. I'm implementing it right now.BTW, will I get any performance increase by changing from bubble sort in my program to the sort API. Or should I try using quick sort?
– user32400
Nov 21 '13 at 19:08
• Timsort is definitely better than all the sorts I know. As for snapping my fingers .. It never worked since Bellatrix, the b**** threw that knife at my chest.
– user32400
Nov 21 '13 at 19:35

I have some doubts about correctness of your code, particularly I am concerned with the fact that implementing step 2 & step 3 of your Logic (from description in your post), you populate array declared as :

String arr[]=new String [b+1];

by only suffixes of your input string, and you don't consider substrings in the middle (non-suffixes). Did you check if your program produces correct results for inputs, such as "123ababa456" ?

Anyway, I decided to put alternative solution below, which is quite easy to follow.
The idea :

Lets denote maximum length of possible solution as currentLen.
currentLen equals n - 1 in the beginning, where n is the length of input.

1. you start by examining all substrings of input with length = currentLen
2. If you find two duplicate strings -> return the result
3. If no results for length currentLen are found - decrement it and go back to step 1.
4. Repeat this loop 1-3 until you found something or your currentLen reached 0

Finding duplicate strings at step 2 is implemented using Set of Strings, which is, very simply put : a data structure which keeps your Strings (with very quick lookup) and tells you if you try to insert a string which was already stored.

I tried to make the code very verbose, but it is still very readable.
I really hope you try to understand it, usage of Set is limited to couple of lines, don't be startled by it.

static String longestRepeatedDna(String input) {

// set containing distinct possible candidates
// when examine new candidate we check if it is already in the set
// if it is -> we found our longest dna!
// in not -> we add the candidate to set and continue
Set<String> dnaSet = new HashSet<String>();

for (int currentLen = input.length() - 1; currentLen > 0; --currentLen) {

// empty before we start processing sub-strings of currentLen
dnaSet.clear();

// examine all substrings of length currentLen
for (int i = 0; i + currentLen <= input.length(); ++i) {
// take substring of length currentLen starting at index i
String possibleDna = input.substring(i, i + currentLen);
if (dnaSet.contains(possibleDna)) {
// hooray! we found it!
return possibleDna;
} else {
}
}
}

// found nothing
return null; // or return "";
}

and test code :

public static void main(String... args) {
String[] testCases = {"ababa", "mababa123", "mytest",};
for (String test : testCases) {
System.out.println("longest dna for input " + test + " = " +
longestRepeatedDna(test));
}
}

Run-time complexity of this solution is O(n^2), and I believe can still be improved.

• It took me a bit to figure out the algorithm, but, it is right. Your "doubts about the correctness" are unfounded... I believe it produces the correct results, and actually the algorithm is quite elegant. Nov 21 '13 at 1:08
• @rolfl "It took me a bit to figure out the algorithm" - you mean OP's algorithm ? About correctness - since actual processing is done on sorted array of suffixes (arr), and that requires searching for duplicate longest substring in that arr, I am curios what is the current complexity of that operation ? Nov 21 '13 at 9:18
• Yes, I mean the OP algorithm. The complexity is messy. I tried an alternate way, but I used 3 loops, although they were all significantly limited. An interesting problem Nov 21 '13 at 11:17
• Thank You for the different approach. As for the correctness of the program, I am getting the desired answer of "aba" when giving your input "123ababa456". Yes, both my original program and the one you suggested are O(n^2) complexity but if I use quick sort, I think I can improve performance since its average case complexity is O(nlogn).
– user32400
Nov 21 '13 at 19:15

It looks to me that the running time is O(|S|2), (where |S| is the length of the string), which would probably make it unusable for analyzing longs strings of DNA.

The standard approach to solving the longest repeated substring problem is to use a suffix tree. The running time of that algorithm should be O(|S|).

To be honest, I found your code difficult to follow, so I haven't read all of it, but there are also some serious issues that I've found.

You do a variant of bubble sort to sort arr. First, bubble sort should be avoided because it is inefficient — O(n2). Second, why is that code cluttering main()? Anything that can be considered a namable operation should be extracted into its own function. Third, common operations like sorting would already be provided by the standard Java library. Take the time to look for it so that you don't reinvent the wheel.

Your check(String a, String b) function is incredibly repetitive. Surely you could find a way to avoid writing the same code twice? (Either swap a and b early in the function, or have the function call itself with the arguments reversed.) Also, what happens if a and b are the same length?

• Ditto to most of your comments. As for the 'a' and 'b' being the same length, I saw that one too, but then realized that, due to the way the values are constructed, it's not possible for them to be the same length. Nov 21 '13 at 4:34
• Then an assert a.length() != b.length() would be helpful. Nov 21 '13 at 5:22
• @200_success ->Thank You for the suggestions.Yes, I will definitely change my bubble sort to quick sort to improve efficiency. And, my professor too told us the best way was to solve it using suffix tree , but unfortunately my knowledge of Java is too limited for that. After changing to quick sort I think the program will be okay since the suffix tree is complexity O(n) and my program will be O(n log n). It should be enough for the 10k input given. On bubble sort it takes 4 seconds. Maybe I can cut that down to 3 or even 2 with quick sort.
– user32400
Nov 21 '13 at 19:20