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

Question

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
    }
}

Answer 1

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.

---

EDIT Part 2: (had dinner)....

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);
}
}

Answer 2

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 {
                dnaSet.add(possibleDna);
            }
        }
    }

    // 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.

Answer 3

It looks to me that the running time is O(|S|²), (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(n²). 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?