Results 1 to 13 of 13
  1. #1
    abi
    abi is offline Member
    Join Date
    Feb 2013
    Posts
    63
    Rep Power
    0

    Default IndexOutOfBounds error

    I have a .txt file which contains the following data. The first line of data is an integer number n that gives the number of pairs of DNA to follow. Reading one pair of string at a time I need to display the LCS.

    3
    GAAGGTCGAA
    CCTCGGGA
    ATGATGGAC
    GTGATAAGGACCC
    AAATTT
    GGGCCC

    I keep getting this error:
    Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: -1
    at java.lang.String.substring(String.java:1958)
    at DNA_12.LCS(DNA_12.java:46)
    at DNA_12.main(DNA_12.java:32)


    Java Code:
    import java.io.*; 
    import java.util.Scanner;
    
    public class DNA_12
    {
      public static void main(String[] args) throws IOException
        {
          
          Scanner sc = new Scanner( new File("dna.txt"));
          
        
          int n = sc.nextInt();
       
          for(int i = 0; i < n; i++)
          {
             String input1 = sc.nextLine();
             String input2 = sc.nextLine();
       
             String dna1; 
             String dna2;             
    
           if(input1.length() > input2.length())
            {
              dna1 = input1;
              dna2 = input2;
            }
           else
            {
              dna1 = input2;
              dna2 = input1;
            }
              System.out.println(LCS(dna1 , dna2));
            }
            sc.close();
        }
    
        public static String LCS(String dna1, String dna2)
        {
            String temp = "";
            String longest = "";
            int match;
            for (int i = 0; i < dna2.length();i++)
            {
                for (int j = 1; j < (dna2.length() - 1); j++)
                {
                    temp = dna2.substring(i, j);
                    match = dna1.indexOf(temp);
                    if (match != -1)
                    {
                        longest=temp;
                    }
                }
            }
            return longest;
        }
    }
    Last edited by abi; 03-22-2013 at 11:25 PM.

  2. #2
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default Re: Creating an algorithm for finding the Longest Common Sequence

    In future there is no need to start another thread, just keep asking questions in the same one.

    If you do not have to write the code yourself then the String class has two methods that can help: contains and indexOf. If you have to write the code yourself then you need to write a loop that compares each character of one String to each character of the other String. As soon as you find a mismatch you know that substring is not correct. This can be done in a method which returns false as soon as it finds a mismatch.

  3. #3
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default Re: Creating an algorithm for finding the Longest Common Sequence

    BTW your algorithm is not robust. Using your example the substrings of s2 are
    CCTCGGGA
    CCTCGGG
    CCTCGG
    CCTCG
    CCTC
    CCT
    CC
    C
    of which only the last one exists in s1. However the longest sequence is TCG which exists in the middle of s2 and would require dropping chars from both ends of the String.

  4. #4
    abi
    abi is offline Member
    Join Date
    Feb 2013
    Posts
    63
    Rep Power
    0

    Default Re: Creating an algorithm for finding the Longest Common Sequence

    Thank You for that information.

    Exactly, that's why I mentioned I haven't figured out the appropriate way to compare them.

    So, I should convert them to arrays first
    then compare the arrays starting from two going up correct??

    Could you give me a sample code? A simple one.

  5. #5
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default Re: Creating an algorithm for finding the Longest Common Sequence

    There is no need to convert to arrays. Once again the String class has a method that can help. Perhaps you should spend some time reading the API.

  6. #6
    abi
    abi is offline Member
    Join Date
    Feb 2013
    Posts
    63
    Rep Power
    0

    Default Re: Creating an algorithm for finding the Longest Common Sequence

    I am a beginner so maybe I haven't come across those methods yet. I just started a few months ago. Well I have to write the code my self aswell.
    Last edited by abi; 03-22-2013 at 02:46 AM.

  7. #7
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default Re: Creating an algorithm for finding the Longest Common Sequence

    Since you are a beginner that is even more reason to read the API. That is where you found out what methods each class has and what they can do.

  8. #8
    abi
    abi is offline Member
    Join Date
    Feb 2013
    Posts
    63
    Rep Power
    0

    Default Re: Creating an algorithm for finding the Longest Common Sequence

    This probably isn't correct but something of this manner is what your trying to get me to do/understand right?
    Java Code:
    public class PracDna
    {  
      public static void main(String[] args)
      {
        String s1 = "GAAGGTCGAA";
        String s2 = "CCTCGGGA";
    
        int s2Length = s2.length();
        int s1Length = s1.length();
    
        for(int i = 0; i < s2Length; i++)
        {
           String s2SubString = s2.substring(0,s2Length - i);
           int index = index(s2SubString, s1);
    
           if( index > 0 )
            {
              System.out.print(s2SubString);
            }
        }
      }
    
      public static int index(String string1, String string2 )
      {
         return string2.indexOf(string1);
      }
    }

  9. #9
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default Re: Creating an algorithm for finding the Longest Common Sequence

    You might want to make the if statement >= 0 since 0 is the index of the first char in a String.

  10. #10
    abi
    abi is offline Member
    Join Date
    Feb 2013
    Posts
    63
    Rep Power
    0

    Default Re: Creating an algorithm for finding the Longest Common Sequence

    Ok. Could you help me with creating the substrings for s2? I can't figure out how to do it properly.

  11. #11
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default Re: Creating an algorithm for finding the Longest Common Sequence

    Spam! Spam! Spam! Spam!

    Recursion would probably work but I guess that is beyond your level of knowledge as yet. Try nested loops then instead of making smaller substrings make longer ones. For example for the String "ABCD" you would do
    A
    AB
    ABC
    ABCD
    B
    BC
    BCD
    C
    CD
    D

  12. #12
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,361
    Blog Entries
    7
    Rep Power
    20

    Default Re: Creating an algorithm for finding the Longest Common Sequence

    Don't try to reinvent the wheel; the LCS problem is a well known problem and dynamic programming can be of help; see Longest common subsequence problem - Wikipedia, the free encyclopedia.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  13. #13
    abi
    abi is offline Member
    Join Date
    Feb 2013
    Posts
    63
    Rep Power
    0

    Default Re: Creating an algorithm for finding the Longest Common Sequence

    Thanks. I did create a code but I have one small problem with it. It has to do with use of indexOf(). I updated this post if you would like to look at it.

Similar Threads

  1. Need help finding the ECG algorithm
    By CHIDIONYZUZ in forum Java Applets
    Replies: 4
    Last Post: 12-13-2012, 05:30 AM
  2. Help with TreeSet and finding longest string
    By JavaTheHut in forum New To Java
    Replies: 3
    Last Post: 05-04-2011, 10:23 PM
  3. Longest common sequence
    By fam2315 in forum New To Java
    Replies: 8
    Last Post: 04-29-2011, 02:00 AM
  4. Difficulty in finding the right algorithm
    By SolidCobra in forum New To Java
    Replies: 3
    Last Post: 10-05-2008, 11:55 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •