fork(21) download 
  1. /*PROMPT:
  2.  * Consider the problem of searching for genes in DNA sequences using Horspool's algorithm.
  3.  * A DNA sequence is represented by a test on the alphabet (A, C, G, T), and the gene segement
  4.  * is the pattern. Write a Java Program that:
  5.  * inputs DNA sequence and a pattern
  6.  * constructs the shift table for the pattern
  7.  * applies the Horspool's algorithm to locate the pattern in the DNA sequence
  8.  * 
  9.  * Test your program with the following:
  10.  * pattern: TCCTATTCTT (it is chromosome 10)
  11.  * DNA Sequence: TTATAGATCTCGTATTCTTTTATAGATCTCCTATTCTT
  12.  */
  13.  
  14. import java.util.*;
  15.  
  16. class Horspool {
  17.  
  18. /* ShiftTable ALGORITHM
  19.    * Fills the shift table used by Horspool's algorithm
  20.    * Input: Pattern P [0..m-1] and an alphabet of possible characters
  21.    * Output: Table[0..size-1] indexed by the alphabet's characters and 
  22.    *         filled with shift sizes computed with the formula:
  23.    *         t(c) = the pattern's length m, if c is not among the first m-1 characters of the pattern
  24.    *          else, the distance from the rightmost c among the first m-1 characters of the pattern to its last character
  25.    * for i = 0 to size -1 do Table[i] = m
  26.    * for j = 0 to m-2 do Table[P[J]]= m-1-j
  27.    * return Table
  28.    */
  29.    public static int[] ShiftTable(String P) {
  30.       int[] Table = new int[128];
  31.       for (int i = 0; i < 128; i++) {
  32.          Table[i] = -1;
  33.       }
  34.       for (int i = 0; i < P.length()-1; i++) {
  35.          Table[P.charAt(i)] = i;
  36.       }
  37.       return Table;
  38.    }
  39.  
  40.  /*HorspoolMatching(P[0..m-1], T[0..n-1]) ALGORITHM
  41.    * Implements Horspool's algorithm for string matching
  42.    * Input: Pattern P[0..m-1] and text T[0..n-1]
  43.    * Output: The index of the left and of the first matching substring
  44.    *         or -1 if their are no matches
  45.    * ShiftTable(P[0..m-1])  //generate table of shifts
  46.    * i = m-1    //position the pattern's right end
  47.    * while i <= n-1 do
  48.    *      k = 0
  49.    *      while k<= m-1 and P[m-1-k]=T[i-k] do
  50.    *           k += 1
  51.    *      if k = m
  52.    *           return i-m+1
  53.    *      else i = i+Table[T[i]]
  54.    * return -1
  55.    */
  56.    public static int HorspoolMatching (String T, String P) {
  57.      int[] Table;
  58.      int   k, j, m, n;
  59.      n = T.length();
  60.      m = P.length();
  61.      Table = ShiftTable(P);
  62.      k = 0; 
  63.      while ( k < (n-m) ) {
  64.         j = m-1;
  65. 	while ( P.charAt(j) == T.charAt(k+j)) {
  66. 	   j--;	
  67. 	   if ( j < 0 )
  68. 	      return (k);
  69.     }
  70. 	k = k + (m-1) - Table[T.charAt(k+(m-1))];
  71.     } 
  72.      return -1;
  73.   }
  74.  
  75. //a function that runs the HorspoolMatching() function and prints the result.
  76.   public static void main(String[] args) {
  77.      String T;
  78.      String P;
  79.      int q;
  80.      T = "TTATAGATCTCGTATTCTTTTATAGATCTCCTATTCTT";
  81.      P = "TCCTATTCTT";
  82.      q = HorspoolMatching (T, P);
  83.      System.out.println("String " + P + " found at pos: " + q);
  84.  
  85.     //A test using a different pattern from the string.
  86.     /*  T = "TTATAGATCTCGTATTCTTTTATAGATCTCCTATTCTT";
  87.      P = "TCTCGTAT";
  88.      q = HorspoolMatching (T, P);
  89.  
  90.      System.out.println("String " + P + " found at pos: " + q);*/
  91.  
  92.   }
  93. }
Success #stdin #stdout 0.06s 380224KB
comments (?)
stdin 
Standard input is empty
stdout 
String TCCTATTCTT found at pos: -1
https://ideone.com/9IjNjo
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!