Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 11 of 11

Thread: Compress DNA sequence using recursion

  1. #1
    Junior Member
    Join Date
    Nov 2013
    Posts
    9
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default Compress DNA sequence using recursion

    I am suppose to create a recursive method that will compress a DNA sequence. For example;
    DNA.compress("GGCcCTtttTT") => "G2C3T6"

    but my code keeps giving me an
    java.lang.ArrayIndexOutOfBoundsException: -1
    at DNA.compress(DNA.java:41)
    at DNA.compress(DNA.java:44)
    at DNA.compress(DNA.java:34)
    at Test.main(Test.java:36)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Nativ e Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(Native MethodAccessorImpl.java:39)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(De legatingMethodAccessorImpl.java:25)
    at java.lang.reflect.Method.invoke(Method.java:597)
    at edu.rice.cs.drjava.model.compiler.JavacCompiler.ru nCommand(JavacCompiler.java:272)


    for the Test Case tgg

    my code is
     public static String compress(String dna){
        String dnaUpper = dna.toUpperCase();
        char[] dnaArray = dnaUpper.toCharArray();
        int len = dnaArray.length;
     
        if(dnaUpper.length() > 1){
          System.out.println("The char at the end is " + dnaArray[len-1]);
          if((dnaArray[len-1] >= 'A') && (dnaArray[len-1] <= 'Z')){ //if the last entry is a letter
            if(dnaArray[len-1] == dnaArray[len-2]){ //if the last 2 entries match
              return compress(dna.substring(0, dna.length() - 2) + dnaUpper.charAt(dna.length()-1) + "2");
            }else{ //if the last 2 entries don't match
              return compress(dna.substring(0, dna.length() - 2) + dna.charAt(len-1));
            }
     
          }else{ //if the last entry is a number
              if((dnaArray[len-2] >= 'A') && (dnaArray[len-2] <= 'Z')){//if the second last entry is a letter
                if(dnaArray[len-2] == dnaArray[len-3]){ //if the second and third last entires match
                  return compress(dna.substring(0,dna.length()-3) + (Integer.parseInt(""+dnaArray[dnaArray.length -1]) + 1));
                } else{ //if the second and third last entries dont match
                  return compress(dna.substring(0,dna.length()-3) + dna.substring(dna.length()-2));
                }
              }else{//if the second last entry is not a letter
                if(dnaArray[len-3] == dnaArray[len-4]){ //if the third last and 4th last entries match
                  return compress(dna.substring(0,dna.length()-4) + Integer.parseInt(dna.substring(dna.length()-3)) + 1);
                }else{ //third and 4th last entries don't match
                  return compress(dna.substring(0,dna.length()-4) + dna.substring(dna.length()-3));
                }
              }
            }
        }else{
          return dnaUpper;
        }
      }

    if you could help me out, I'd really appreciate it.

    Thanks


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    20,974
    Thanks
    52
    Thanked 2,269 Times in 2,241 Posts

    Default Re: Compress DNA sequence using recursion

    java.lang.ArrayIndexOutOfBoundsException: -1
    at DNA.compress(DNA.java:41)
    At line 41 the code uses an index (-1) that is out of bounds. Valid indexes for arrays range in value from 0 to the array length-1.
    Look at line 41, find the index and then backtrack in the code to see why it had a value of -1.

    The code should validate the value of len and the size of the array before it assumes the indexes it is using are valid.
    If you don't understand my answer, don't ignore it, ask a question.

  3. The Following User Says Thank You to Norm For This Useful Post:

    adamniazi (November 15th, 2013)

  4. #3
    Junior Member
    Join Date
    Nov 2013
    Posts
    9
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default Re: Compress DNA sequence using recursion

    I've modified to code to not give ArrayIndexOutOfBoundsException anymore. But it is still not giving me the correct output. Some letters seem to disappear or get added to ones that dont match.

    new code:

    public static String compress(String dna){
        String dnaUpper = dna.toUpperCase();
        char[] dnaArray = dnaUpper.toCharArray();
        int len = dnaArray.length;
     
        if(dnaUpper.length() > 1){
          System.out.println("The char at the end is " + dnaArray[len-1]);
          if((dnaArray[len-1] >= 'A') && (dnaArray[len-1] <= 'Z')){ //if the last entry is a letter
            if(dnaArray[len-1] == dnaArray[len-2]){ //if the last 2 entries match
              return compress(dna.substring(0, dna.length() - 2) + dnaUpper.charAt(dna.length()-1) + "2");
            }else{ //if the last 2 entries don't match
              return compress(dna.substring(0, dna.length() - 2)) + dna.charAt(len-1);
            }
     
          }else{ //if the last entry is a number
              if((dnaArray[len-2] >= 'A') && (dnaArray[len-2] <= 'Z')){//if the second last entry is a letter
                if(dnaArray[len-2] == dnaArray[len-3]){ //if the second and third last entires match
                  return compress(dna.substring(0,dna.length()-3) + (Integer.parseInt(""+dnaArray[dnaArray.length -1]) + 1));
                } else{ //if the second and third last entries dont match
                  return compress(dna.substring(0,dna.length()-3)) + dna.substring(dna.length()-2);
                }
              }else{//if the second last entry is not a letter
                if(dnaArray[len-3] == dnaArray[len-4]){ //if the third last and 4th last entries match
                  return compress(dna.substring(0,dna.length()-4) + Integer.parseInt(dna.substring(dna.length()-3)) + 1);
                }else{ //third and 4th last entries don't match
                  return compress(dna.substring(0,dna.length()-4)) + dna.substring(dna.length()-3);
                }
              }
            }
        }else{
          return dnaUpper;
        }
      }

  5. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    20,974
    Thanks
    52
    Thanked 2,269 Times in 2,241 Posts

    Default Re: Compress DNA sequence using recursion

    Have you tried debugging the code to see what it is doing? Add some println() statements that print out the values of variables as their values are changed so you can see what the code is doing.
    The Arrays class's toString() method is useful:
    System.out.println("an ID "+ java.util.Arrays.toString(theArrayName));
    If you don't understand my answer, don't ignore it, ask a question.

  6. The Following User Says Thank You to Norm For This Useful Post:

    adamniazi (November 15th, 2013)

  7. #5
    Junior Member
    Join Date
    Nov 2013
    Posts
    9
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default Re: Compress DNA sequence using recursion

    So I've got pretty much everything working, except when I start getting double digits. The new code is at the bottom and the part that handles the double digits is bolded. I've code it working well if for example i use a string 10 letters long of a, But if I use 20 letters of A, i would expect A20, but I get A8101. Cannot figure this last part out.

    public static String compress(String dna){
        String dnaUpper = dna.toUpperCase();
        System.out.println("The String entered is: " + dnaUpper);
        char[] dnaArray = dnaUpper.toCharArray();
        int len = dnaArray.length;
     
        if(dnaUpper.length() > 1){
          System.out.println("The char at the end is " + dnaArray[len-1]);
          if((dnaArray[len-1] >= 'A') && (dnaArray[len-1] <= 'Z')){ //if the last entry is a letter
            System.out.println("The last Entry is a letter");
            if(dnaArray[len-1] == dnaArray[len-2]){ //if the last 2 entries match
              System.out.println("The last 2 entries match");
              System.out.println("Returned is: "+ "compress(" + dna.substring(0, dna.length() - 2) + "+" + dnaUpper.charAt(dna.length()-1) + "+" +"2)");
              return compress(dna.substring(0, dna.length() - 2) + dnaUpper.charAt(dna.length()-1) + "2");
            }else{ //if the last 2 entries don't match
              System.out.println("Last 2 entries dont's match");
              System.out.println("returned is: " + "compress("+dna.substring(0, dna.length() - 1)+")" + " +" + dnaUpper.charAt(len-1));
              return compress(dna.substring(0, dna.length() - 1)) + dnaUpper.charAt(len-1);
            }
     
          }else{ //if the last entry is a number
            System.out.println("The character at the end is a number");
              if((dnaArray[len-2] >= 'A') && (dnaArray[len-2] <= 'Z')){//if the second last entry is a letter
                System.out.println("the 2nd last entry is a letter");
                if(dna.length() ==2){
                  System.out.println("length = 2");
                  System.out.println("returned: " + dnaUpper);
                  return dnaUpper;
                }else if(dnaArray[len-2] == dnaArray[len-3]){ //if the second and third last entires match
                  System.out.println("the second and third last match");
                  System.out.println("returned is: compress(" + dna.substring(0,dna.length()-2)+"+" + (Integer.parseInt(""+dnaArray[dnaArray.length -1]) + 1));
                  return compress(dna.substring(0,dna.length()-2) + (Integer.parseInt(""+dnaArray[dnaArray.length -1]) + 1));
                } else{ //if the second and third last entries dont match
                  System.out.println("the second and third last entries dont match");
                  System.out.println("returned is: " + "compress("+dna.substring(0,dna.length()-2)+ ")+" + dna.substring(dna.length()-2));
                  return compress(dna.substring(0,dna.length()-2)) + dna.substring(dna.length()-2);
                }
              }[B]else{//if the second last entry is not a letter
                System.out.println("the second last character is not a letter");
                if(dna.length() ==3){
                  System.out.println("length = 3");
                  System.out.println("returned: " + dnaUpper);
                  return dnaUpper;
              }else if(dnaArray[len-3] == dnaArray[len-4]){ //if the third last and 4th last entries match
                  System.out.println("returned: compress(" + dna.substring(0,dna.length()-4)+"+" + Integer.parseInt(dna.substring(dna.length()-2)) + 1);
                  return compress(dna.substring(0,dna.length()-4) + Integer.parseInt(dna.substring(dnaUpper.length()-2)) + 1);
                }else{ //third and 4th last entries don't match
                  return compress(dna.substring(0,dna.length()-4)) + dna.substring(dna.length()-3);
                }
              }
            }[/B]
        }else{
          return dnaUpper;
        }
      }

    Edit: I cannot bold any part of the code so its the part near the end between [B and /B], thanks

  8. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    20,974
    Thanks
    52
    Thanked 2,269 Times in 2,241 Posts

    Default Re: Compress DNA sequence using recursion

    Can you post the program's output that shows what you are talking about?
    How can the code be tested? It doesn't have a class and a main() method.
    If you don't understand my answer, don't ignore it, ask a question.

  9. #7
    Junior Member
    Join Date
    Nov 2013
    Posts
    9
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default Re: Compress DNA sequence using recursion

    these are the tests i'm running, from a different class

    String a1 = "";
    String b1 = DNA.compress(a1);
    System.out.println(b1);

    String a3 = "Cat";
    String b3 = DNA.compress(a3);
    System.out.println("tgg: "+ b3);

    String a2 = "GGCcCTtttTT";
    String b2 = DNA.compress(a2);
    System.out.println("ggtttaaaaccccccttttgtgtttgactg : " + b2);

    String a4 = "aaaaaaaaaaaaaaaaaaaa";
    String b4 = DNA.compress(a4);
    System.out.println("expect A20, got: " + b4);

  10. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    20,974
    Thanks
    52
    Thanked 2,269 Times in 2,241 Posts

    Default Re: Compress DNA sequence using recursion

    That looks like source code, not the program's output.
    How can the code be tested? It needs a class with a main() method.
    If you don't understand my answer, don't ignore it, ask a question.

  11. #9
    Junior Member
    Join Date
    Nov 2013
    Posts
    9
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default Re: Compress DNA sequence using recursion

    test class:

    public class Test{
      public static void main(String[] args){
        String a1 = "";
        String b1 = DNA.compress(a1);
        System.out.println(b1);
     
        String a3 = "Cat";
        String b3 = DNA.compress(a3);
        System.out.println("tgg: "+ b3);
     
        String a2 = "GGCcCTtttTT";
        String b2 = DNA.compress(a2);
        System.out.println("ggtttaaaaccccccttttgtgtttgactg: " + b2);
     
        String a4 = "baaaaaaaaaaaaaaaaaaaa";
        String b4 = DNA.compress(a4);
        System.out.println("expect BA20, got: " + b4);
     
      }
     
    }

    DNA class(updated):
    public class DNA{
     
      /******************************************************************** 
        public static String compress(String dna)
     
        input: a non-null string consisting only of the letters G,A,T and C.
              (this is the long form representation)
              (they may be upper, lower, or mixed case)
        output: a string that represents a condensed version of the input string.  
                o) Each occurrence of a single letter (its neighbours are different) 
                   is copied to the new string. 
                o) Each occurrence of a sequence of a single letter that
                   is repeated two or more times is replaced by
                   that letter and number of occurrences in the new string
                All letters in the output should be capitalized.
        examples: DNA.compress("GGCcCTtttTT") => "G2C3T6"
                  DNA.compress("Cat")         => "CAT"
                  DNA.compress("")            => ""     
      *********************************************************************/
      public static String compress(String dna){
        String dnaUpper = dna.toUpperCase();
        System.out.println("The String entered is: " + dnaUpper);
        char[] dnaArray = dnaUpper.toCharArray();
        int len = dnaArray.length;
     
        if(dnaUpper.length() > 1){
          System.out.println("The char at the end is " + dnaArray[len-1]);
          if((dnaArray[len-1] >= 'A') && (dnaArray[len-1] <= 'Z')){ //if the last entry is a letter
            System.out.println("The last Entry is a letter");
            if(dnaArray[len-1] == dnaArray[len-2]){ //if the last 2 entries match
              System.out.println("The last 2 entries match");
              System.out.println("Returned is: "+ "compress(" + dna.substring(0, dna.length() - 2) + "+" + dnaUpper.charAt(dna.length()-1) + "+" +"2)");
              return compress(dna.substring(0, dna.length() - 2) + dnaUpper.charAt(dna.length()-1) + "2");
            }else{ //if the last 2 entries don't match
              System.out.println("Last 2 entries dont's match");
              System.out.println("returned is: " + "compress("+dna.substring(0, dna.length() - 1)+")" + " +" + dnaUpper.charAt(len-1));
              return compress(dna.substring(0, dna.length() - 1)) + dnaUpper.charAt(len-1);
            }
     
          }else{ //if the last entry is a number
            System.out.println("The character at the end is a number");
              if((dnaArray[len-2] >= 'A') && (dnaArray[len-2] <= 'Z')){//if the second last entry is a letter
                System.out.println("the 2nd last entry is a letter");
                if(dna.length() ==2){
                  System.out.println("length = 2");
                  System.out.println("returned: " + dnaUpper);
                  return dnaUpper;
                }else if(dnaArray[len-2] == dnaArray[len-3]){ //if the second and third last entires match
                  System.out.println("the second and third last match");
                  System.out.println("returned is: compress(" + dna.substring(0,dna.length()-2)+"+" + (Integer.parseInt(""+dnaArray[dnaArray.length -1]) + 1));
                  return compress(dna.substring(0,dna.length()-2) + (Integer.parseInt(""+dnaArray[dnaArray.length -1]) + 1));
                } else{ //if the second and third last entries dont match
                  System.out.println("the second and third last entries dont match");
                  System.out.println("returned is: " + "compress("+dna.substring(0,dna.length()-2)+ ")+" + dna.substring(dna.length()-2));
                  return compress(dna.substring(0,dna.length()-2)) + dna.substring(dna.length()-2);
                }
              }else{//if the second last entry is not a letter
                System.out.println("the second last character is not a letter");
                if(dna.length() ==3){
                  System.out.println("length = 3");
                  System.out.println("returned: " + dnaUpper);
                  return dnaUpper;
              }else if(dnaArray[len-3] == dnaArray[len-4]){ //if the third last and 4th last entries match
                int x = Integer.parseInt(dna.substring(dna.length()-2));
                int y = x + 1;
                  System.out.println("returned: compress(" + dna.substring(0,dna.length()-3)+"+" + x+"+" + 1);
                  System.out.println("Integer.parseInt(dna.substring(dna.length()-2))="+ x +" + 1 = "+ y);
                  return compress(dna.substring(0,dna.length()-3) + y);
                }else{ //third and 4th last entries don't match
                  return compress(dna.substring(0,dna.length()-4)) + dna.substring(dna.length()-3);
                }
              }
            }
        }else{
          return dnaUpper;
        }
      }

    results
    Cat: CAT
    GGCcCTtttTT: G2C3T6
    expect A20, got: A20
    Expect BA20: got: a20

    --- Update ---

    ok so I got it working, here's the code I've used to compress DNA sequence recursively. Thank for all your help guys:

    public static String compress(String dna){
        String dnaUpper = dna.toUpperCase();
        System.out.println("The String entered is: " + dnaUpper);
        char[] dnaArray = dnaUpper.toCharArray();
        int len = dnaArray.length;
     
        if(dnaUpper.length() > 1){
          System.out.println("The char at the end is " + dnaArray[len-1]);
          if((dnaArray[len-1] >= 'A') && (dnaArray[len-1] <= 'Z')){ //if the last entry is a letter
            System.out.println("The last Entry is a letter");
            if(dnaArray[len-1] == dnaArray[len-2]){ //if the last 2 entries match
              System.out.println("The last 2 entries match");
              System.out.println("Returned is: "+ "compress(" + dna.substring(0, dna.length() - 2) + "+" + dnaUpper.charAt(dna.length()-1) + "+" +"2)");
              return compress(dna.substring(0, dna.length() - 2) + dnaUpper.charAt(dna.length()-1) + "2");
            }else{ //if the last 2 entries don't match
              System.out.println("Last 2 entries dont's match");
              System.out.println("returned is: " + "compress("+dna.substring(0, dna.length() - 1)+")" + " +" + dnaUpper.charAt(len-1));
              return compress(dna.substring(0, dna.length() - 1)) + dnaUpper.charAt(len-1);
            }
     
          }else{ //if the last entry is a number
            System.out.println("The character at the end is a number");
              if((dnaArray[len-2] >= 'A') && (dnaArray[len-2] <= 'Z')){//if the second last entry is a letter
                System.out.println("the 2nd last entry is a letter");
                if(dna.length() ==2){
                  System.out.println("length = 2");
                  System.out.println("returned: " + dnaUpper);
                  return dnaUpper;
                }else if(dnaArray[len-2] == dnaArray[len-3]){ //if the second and third last entires match
                  System.out.println("the second and third last match");
                  System.out.println("returned is: compress(" + dna.substring(0,dna.length()-2)+"+" + (Integer.parseInt(""+dnaArray[dnaArray.length -1]) + 1));
                  return compress(dna.substring(0,dna.length()-2) + (Integer.parseInt(""+dnaArray[dnaArray.length -1]) + 1));
                } else{ //if the second and third last entries dont match
                  System.out.println("the second and third last entries dont match");
                  System.out.println("returned is: " + "compress("+dna.substring(0,dna.length()-2)+ ")+" + dna.substring(dna.length()-2));
                  return compress(dna.substring(0,dna.length()-2)) + dna.substring(dna.length()-2);
                }
              }else{//if the second last entry is not a letter
                System.out.println("the second last character is not a letter");
                if(dna.length() ==3){
                  System.out.println("length = 3");
                  System.out.println("returned: " + dnaUpper);
                  return dnaUpper;
              }else if(dnaArray[len-3] == dnaArray[len-4]){ //if the third last and 4th last entries match
                int x = Integer.parseInt(dna.substring(dna.length()-2));
                int y = x + 1;
                  System.out.println("returned: compress(" + dna.substring(0,dna.length()-3)+"+" + x+"+" + 1);
                  System.out.println("Integer.parseInt(dna.substring(dna.length()-2))="+ x +" + 1 = "+ y);
                  return compress(dna.substring(0,dna.length()-3) + y);
                }else{ //third and 4th last entries don't match
                  System.out.println("compress(dna.substring(0,dna.length()-3)) = " + dnaUpper.substring(0,dnaUpper.length()-3) +" + " + "dnaUpper.substring(dna.length()-3)=" + dnaUpper.substring(dnaUpper.length()-3));
                  return compress(dnaUpper.substring(0,dnaUpper.length()-3)) + dnaUpper.substring(dnaUpper.length()-3);
                }
              }
            }
        }else{
          return dnaUpper;
        }
      }

  12. #10
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    20,974
    Thanks
    52
    Thanked 2,269 Times in 2,241 Posts

    Default Re: Compress DNA sequence using recursion

    This line of output looks like the desired results:
    The String entered is: BA20
    If you don't understand my answer, don't ignore it, ask a question.

  13. The Following User Says Thank You to Norm For This Useful Post:

    adamniazi (November 15th, 2013)

  14. #11
    Junior Member
    Join Date
    Nov 2013
    Posts
    9
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default Re: Compress DNA sequence using recursion

    Thanks for the help, I got it working and posted the working code above.

Similar Threads

  1. [SOLVED] How to I possibly compress a java string to say byte space?
    By redbull in forum What's Wrong With My Code?
    Replies: 25
    Last Post: January 15th, 2013, 09:01 AM
  2. how can i compress a video file for example an avi file in java?
    By vigneshwaran in forum Java Theory & Questions
    Replies: 1
    Last Post: January 15th, 2013, 01:39 AM
  3. Compress my Code!
    By aStudentofJava in forum Loops & Control Statements
    Replies: 23
    Last Post: March 4th, 2012, 05:14 AM
  4. Compress Ipv6 Addresses
    By abhay8nitt in forum Java Networking
    Replies: 5
    Last Post: May 20th, 2010, 06:58 AM

Tags for this Thread