public class GapCosts {

    public float open;
    public float extend;

    public GapCosts(float open, float extend) {
        this.open = open;
        this.extend = extend;
    }

    @Override
    public String toString() {
        return "XO:i:"+(int) open + "\tXE:i:" + (int) extend;
    }
} public class Genome {

    private String sequence;
    private String header;
    private Map<String, List<Integer>> kmerMap = new HashMap<>();

    /**
     *
     * @param sequence
     * @throws IllegalStateException
     */
    public Genome(String sequence) throws IllegalStateException {
        this.sequence = sequence;
        this.split();
    }

    /**
     *
     * @param hap
     * @throws IllegalStateException
     */
    public Genome(Map.Entry<String, String> hap) throws IllegalStateException {
        this.sequence = hap.getKey();
        this.header = hap.getValue().replaceAll(">", "").replace(" ", "");
    }

    public void split() throws IllegalStateException {
        for (int i = Globals.KMER_LENGTH; i <= this.sequence.length(); i++) {
            String tmp = this.sequence.substring(i - Globals.KMER_LENGTH, i);
            if (kmerMap.containsKey(tmp)) {
                kmerMap.get(tmp).add(i - Globals.KMER_LENGTH + 1);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(i - Globals.KMER_LENGTH + 1);
                kmerMap.put(tmp, list);
            }
        }
    }

    /**
     *
     * @return
     */
    public Map<String, List<Integer>> getKmerMap() {
        return Collections.unmodifiableMap(kmerMap);
    }

    /**
     *
     * @return
     */
    public String getSequence() {
        return sequence;
    }

    /**
     *
     * @return
     */
    public String getHeader() {
        return header;
    }
} public class Globals {

    public static boolean NO_HASHING;
    public static boolean SENSITIVE;
    public static boolean CONSENSUS;
    public static int READCOUNTER = 0;
    public static int STEPS;
    public static List<SequenceEntry> TRASH_READS = new CopyOnWriteArrayList<>();
    public static boolean RM_DEL;
    public static boolean REFINE;
    public static boolean FILTER;
    public static boolean FLAT;
    public static float GOP;
    public static float GEX;
    public static double MAX_DEL;
    public static double MAX_INS;
    public static double MAX_SUB;
    public static boolean KEEP;
    public static List<Read> READS;
    public static int MAX_CONSECUTIVE_DEL;
    public static int MIN_LENGTH_ALIGNED;
    public static int MIN_LENGTH;
    public static int GENOME_LENGTH;
    public static int THRESHOLD;
    public static String[] GENOME_SEQUENCES;
    public static boolean ADJUST;
    public static boolean SAVE;
    public static int GENOME_COUNT;
    public static Genome[] GENOMES;
    public static int CUT = 0;
    public static int KMER_OVERLAP = 10;
    public static int KMER_LENGTH = 1;
    public static final ForkJoinPool fjPool = new ForkJoinPool();
    public static int N = 0;
    public static int maxN = 0;
    public static double PERCENTAGE_PROCESSING_READS = 0;
    public static double PERCENTAGE_EXTRACTING_READS = 0;
    public static double UNIDENTICAL = 0;
    public static String output = System.getProperty("user.dir") + File.separator;
    public static Matrix MATRIX = loadMatrix();
    public static int[] RS;
    public static String[] ADAPTER;
    public static double PLURALITY;
    public static double PLURALITY_N;
    public static int MIN_CONS_COV = 0;
    public static double Q;
    public static double REALIGN;

    /**
     *
     * @return
     */
    public static Matrix loadMatrix() {
        Matrix m = null;
        try {
            m = MatrixLoader.load("EDNAFULL");
        } catch (MatrixLoaderException ex) {
            System.err.println("Matrix error loading");
        }
        return m;
    }

    public static void printPercentageExtractingReads() {
        PERCENTAGE_EXTRACTING_READS += 100d / N;
        StatusUpdate.print("Extracting reads:\t", PERCENTAGE_EXTRACTING_READS);
    }

    public static void printPercentageProcessingReads() {
        PERCENTAGE_PROCESSING_READS += 100d / N;
        StatusUpdate.print("Processing reads:\t", PERCENTAGE_PROCESSING_READS);
    }
} public class Kmer implements Serializable {

    private String sequence;
    private int number;

    /**
     *
     * @return
     */
    public boolean isMapped() {
        return mapped;
    }

    /**
     *
     * @param mapped
     */
    public void setMapped(boolean mapped) {
        this.mapped = mapped;
    }
    private boolean mapped = false;

    /**
     *
     * @param sequence
     * @param number
     */
    public Kmer(String sequence, int number) {
        this.sequence = sequence;
        this.number = number;
    }

    /**
     *
     * @return
     */
    public int getNumber() {
        return number;
    }

    /**
     *
     * @return
     */
    public String getSequence() {
        return sequence;
    }
} public class Read implements Serializable {

    private String read;
    private List<Kmer> kmers;
    private Hits[] hits;
    private int begin;
    private int end;
    private String alignedRead;
    private int number;
    private boolean reverse;
    private String quality;
    private String header;
    private int bestGenomeIndex = -1;
    private String cigars;
    private Object alignmentScore;
    private String gapCosts;
    private int pairedNumber;

    public Read(int begin, int end, String alignedRead) {
        super();
        this.begin = begin;
        this.end = end;
        this.alignedRead = alignedRead;
    }

    public Read(String read, int number, boolean reverse) {
        this.read = read;
        this.number = number;
        this.reverse = reverse;
//        this.quality = quality;
        this.kmers = new ArrayList<>();
        this.init();
        this.split();
    }

    public Read(String read, int number, String quality, boolean reverse) {
        this.read = read;
        this.number = number;
        this.reverse = reverse;
        this.quality = quality;
        this.kmers = new ArrayList<>();
        this.init();
        this.split();
    }

    private void init() {
        this.hits = new Hits[Globals.GENOME_COUNT];
        for (int i = 0; i < Globals.GENOME_COUNT; i++) {
            this.hits[i] = new Hits();
        }
    }

    private void split() {
        int location = 0;
        for (int i = Globals.KMER_LENGTH; i <= read.length(); i += Globals.KMER_OVERLAP) {
            this.kmers.add(new Kmer(this.read.substring(i - Globals.KMER_LENGTH, i), location++));
        }
    }

    public void findMaxHitRegion() {
        for (int x = 0; x < hits.length; x++) {
            Hits h = hits[x];
            int currentHits = 0;
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < Globals.GENOME_SEQUENCES[x].length(); i++) {
                currentHits += getHit(i, x);
                sb.append(getHit(i, x)).append(" ");
                if (i >= (h.min + read.length())) {
                    if (currentHits > h.maximumHits) {
                        h.region[0] = i - read.length();
                        h.region[1] = i;
                        h.maximumHits = currentHits;
                    }
                    currentHits -= getHit(i - read.length(), x);
                }
            }
//            Utils.saveFile(Globals.output + this.header + ".hits", sb.toString());
            if (currentHits > h.maximumHits) {
                h.region[0] = Globals.GENOME_SEQUENCES[x].length() - read.length();
                h.region[1] = Globals.GENOME_SEQUENCES[x].length();
                h.maximumHits = currentHits;
            }
        }
    }

    public void addHit(int from, int to, int genome) {
        Hits h = hits[genome];
        h.min = Math.min(from, h.min);
        h.max = Math.max(to, h.max);
        for (int i = from; i < to; i++) {
            if (h.hitMap.containsKey(i)) {
                h.hitMap.put(i, h.hitMap.get(i) + i);
            } else {
                h.hitMap.put(i, 1);
            }
        }
    }

    public int getHit(int i, int genome) {
        Hits h = hits[genome];
        if (h.hitMap.containsKey(i)) {
            return h.hitMap.get(i);
        } else {
            return 0;
        }
    }

    public void cut(int from) {
        char[] cs = this.cigars.toCharArray();
        int preoffset = 0;
        for (int i = 0; i < from; i++) {
            if (cs[i] == 'D') {
                preoffset--;
            }
        }
        this.cigars = this.cigars.substring(from);
        this.alignedRead = this.alignedRead.substring(preoffset + from);
        if (this.quality != null) {
            this.quality = this.quality.substring(from);
        }
    }

    public void cut(int from, int to) {
        char[] cs = this.cigars.toCharArray();
        int preoffset = 0;
        for (int i = 0; i < from; i++) {
            if (cs[i] == 'D') {
                preoffset--;
//            } else if (cs[i] == 'I') {
//                preoffset++;
            }
        }

        this.cigars = this.cigars.substring(from, to);
        int offset = 0;
        for (char c : this.cigars.toCharArray()) {
            if (c == 'D') {
                offset--;
//            } else if (c == 'I') {
//                offset++;
            }
        }
        int l = this.alignedRead.length();
        this.alignedRead = this.alignedRead.substring(preoffset + from, offset + to);
        if (this.quality != null) {
            this.quality = this.quality.substring(from, to);
        }
    }

    /**
     *
     * @return
     */
    public List<Kmer> getKmers() {
        return Collections.unmodifiableList(kmers);
    }

    /**
     *
     * @return
     */
    public String getRead() {
        return read;
    }

    /**
     *
     * @return
     */
    public int getBegin() {
        return begin;
    }

    /**
     *
     * @param begin
     */
    public void setBegin(int begin) {
        this.begin = begin;
    }

    /**
     *
     * @return
     */
    public int getEnd() {
        return end;
    }

    /**
     *
     * @param end
     */
    public void setEnd(int end) {
        this.end = end;
    }

    /**
     *
     * @return
     */
    public int getBestFittingGenome() {
        if (this.bestGenomeIndex == -1) {
            int maximumHits = 0;
            for (int i = 0; i < hits.length; i++) {
                Hits h = hits[i];
                if (maximumHits < h.maximumHits) {
                    maximumHits = h.maximumHits;
                    bestGenomeIndex = i;
                }
            }
        }
//        if (this.bestGenomeIndex == -1) {
//            System.out.println("");
//        }
        return bestGenomeIndex;
    }

    /**
     *
     * @return
     */
    public int getMaximumHits() {
        if (this.getBestFittingGenome() == -1) {
            return -1;
        }
        return hits[this.getBestFittingGenome()].maximumHits;
    }

    /**
     *
     * @return
     */
    public int[] getRegion() {
        return hits[this.getBestFittingGenome()].region;
    }

    /**
     *
     * @param genome
     * @return
     */
    public int[] getRegion(int genome) {
        return hits[genome].region;
    }

    /**
     *
     * @return
     */
    public String getAlignedRead() {
        return alignedRead;
    }

    /**
     *
     * @return
     */
    public boolean isAligned() {
        return alignedRead != null;
    }

    /**
     *
     * @param alignedRead
     */
    public void setAlignedRead(String alignedRead) {
        this.alignedRead = alignedRead;
    }

    /**
     *
     * @return
     */
    public boolean isReverse() {
        return reverse;
    }

    /**
     *
     * @return
     */
    public int getNumber() {
        return number;
    }

    /**
     *
     * @return
     */
    public String getQuality() {
        return quality;
    }

    /**
     *
     * @param quality
     */
    public void setQuality(String quality) {
        this.quality = quality;
    }

    public void setCigars(char[] cigars) {
        StringBuilder cigarSB = new StringBuilder();
        for (char c : cigars) {
            cigarSB.append(c);
        }

        this.cigars = cigarSB.toString();
    }

    public String getCigars() {
        StringBuilder cigarSB = new StringBuilder();
        char prev = 'x';
        int count = 0;
        for (char c : cigars.replaceAll("X", "M").toCharArray()) {
            if (c != 0) {
                if (prev == 'x') {
                    prev = c;
                    count++;
                } else {
                    if (c == prev) {
                        count++;
                    } else {
                        cigarSB.append(count).append(prev);
                        prev = c;
                        count = 1;
                    }
                }
            }
        }
        cigarSB.append(count).append(prev);
        return cigarSB.toString();
    }

    public char[] getCigarsPure() {
        return cigars.toCharArray();
    }

    public String getHeader() {
        return header;
    }

    public void setHeader(String header) {
        this.header = header;
    }

    public void setNumber(int number) {
        this.number = number;
    }

    public String toString(Read paired) {
        StringBuilder sb = new StringBuilder();
//        sb.append("R");
        if (this.getHeader() != null) {
            sb.append(this.getHeader().split(" ")[0].substring(1));
        } else {
            sb.append("READ_").append(Globals.READCOUNTER++);
        }
//        if (Globals.CONSENSUS) {
//            sb.append("\t0\t").append("CONSENSUS");
//        } else {
        int flag = 0x0;
        if (paired != null) {
            flag |= 0x1;
            flag |= 0x2;
            if (this.reverse) {
                flag |= 0x10;
            }
            if (paired.reverse) {
                flag |= 0x20;
            }
            if (this.begin == paired.begin) {
                if (!this.reverse) {
                    flag |= 0x40;
                } else {
                    flag |= 0x80;
                }
            } else if (this.begin < paired.begin) {
                flag |= 0x40;
            } else {
                flag |= 0x80;
            }
        } else {
            if (this.reverse) {
                flag |= 0x10;
            }
        }
        sb.append("\t").append(flag);
        sb.append("\t").append(Globals.GENOMES[this.getBestFittingGenome()].getHeader());
//        }
        sb.append("\t").append(this.getBegin());
        sb.append("\t").append(60);
        sb.append("\t").append(this.getCigars());
        if (paired == null) {
            sb.append("\t").append("*");
            sb.append("\t").append("0");
            sb.append("\t").append("0");
        } else {
            sb.append("\t").append(Globals.GENOMES[this.getBestFittingGenome()].getHeader().equals(Globals.GENOMES[paired.getBestFittingGenome()].getHeader()) ? "=" : "*");
            sb.append("\t").append(paired.begin);
            sb.append("\t");
            if (this.reverse) {
                sb.append("-");
            }
            if (paired.begin < this.begin) {
                sb.append((this.end - paired.begin));
            } else {
                sb.append((paired.end - this.begin));
            }
        }
        sb.append("\t").append(this.getAlignedRead());
        sb.append("\t");
        if (this.getQuality() != null && !this.getQuality().isEmpty()) {
            for (int i = 0; i < this.getQuality().length(); i++) {
                sb.append((char) this.getQuality().charAt(i));
            }
        } else {
            sb.append("*");
        }
        sb.append("\t").append("AS:i:").append(this.alignmentScore);
        sb.append("\t").append("NM:i:").append(StringUtils.countMatches(cigars, "X"));
        sb.append("\t").append(this.gapCosts);
        sb.append("\n");
        return sb.toString();
    }

    public Object getAlignmentScore() {
        return alignmentScore;
    }

    public void setAlignmentScore(int as) {
        this.alignmentScore = as;// > 255 ? 255 : mapq;
    }

    public String getGapCosts() {
        return gapCosts;
    }

    public void setGapCosts(String gapCosts) {
        this.gapCosts = gapCosts;
    }

    public int getPairedNumber() {
        return pairedNumber;
    }

    public void setPairedNumber(int pairedNumber) {
        this.pairedNumber = pairedNumber;
    }
} public class SequenceEntry {

    public String sequence;
    public String header;
    public String quality;
    public int startOffset;
    public int endOffset;
    public int pairedNumber = -1;

    public SequenceEntry(String sequence, String header, String quality, int startOffset, int endOffset) {
        this.sequence = sequence;
        this.header = header;
        this.quality = quality;
        this.startOffset = startOffset;
        this.endOffset = endOffset;
    }

    public SequenceEntry(String sequence, String header, String quality) {
        this.sequence = sequence;
        this.header = header;
        this.quality = quality;
    }

    /**
     *
     * @param sequence
     */
    public SequenceEntry(String sequence) {
        this.sequence = sequence;
    }

    public SequenceEntry(String sequence, String quality) {
        this.sequence = sequence;
        this.quality = quality;
    }
    
    public SequenceEntry(SimpleRead sr) {
        this.sequence = sr.read;
        this.quality = sr.quality;
    }
} public class StatusUpdate {

    private static final long start = System.currentTimeMillis();
    private static final DateFormat df;
    public static int readCount = 0;
    public static int unmappedCount = 0;
    public static int tooSmallCount = 0;
    public static int alignCount1 = 0;
    public static int alignCount2 = 0;
    public static int alignCount3 = 0;
    private static String oldOut = "";

    static {
        df = new SimpleDateFormat("HH:mm:ss");
        df.setTimeZone(TimeZone.getTimeZone("GMT"));
    }

    public static void print(String text, double percentage) {
        System.out.print("\r" + time() + "  " + text + Math.round(percentage * 100) / 100 + "%");
    }

    public static void print(String text) {
        System.out.print("\r" + time() + "  " + text);
    }

    public synchronized static void processReads() {
        readCount++;
        if (!oldOut.equals(time())) {
            oldOut = time();
            System.out.print("\r                                                                                                                      ");
            System.out.print("\r" + time() + " Mapped: " + readCount + "\t\tUnmapped: " + unmappedCount + "\t\tToo small: " + tooSmallCount);
        }
    }

    public synchronized static void processUnmapped() {
        ++unmappedCount;
        if (!oldOut.equals(time())) {
            oldOut = time();
            System.out.print("\r                                                                                                                     ");
            System.out.print("\r" + time() + " Mapped: " + (readCount) + "\t\tUnmapped: " + unmappedCount + "\t\tToo small: " + tooSmallCount);
        }
    }

    public synchronized static void processLength() {
        ++tooSmallCount;
        if (!oldOut.equals(time())) {
            oldOut = time();
            System.out.print("\r                                                                                                                     ");
            System.out.print("\r" + time() + " Mapped: " + (readCount) + "\t\tUnmapped: " + unmappedCount + "\t\tToo small: " + tooSmallCount);
        }
    }

    public static void println(String text) {
        System.out.println("\r" + time() + "  " + text);
    }

    private static String time() {
        return df.format(new Date(System.currentTimeMillis() - start));
    }
}
 public class Utils {

    public static List<SequenceEntry> splitRead(SequenceEntry se) {
        final int splitLength = 400;
        List<SequenceEntry> list = new LinkedList<>();
        int l = se.sequence.length();
        if (l > splitLength) {
            for (int i = 0; i < l; i += splitLength) {
                int end;
                if (i + splitLength > l) {
                    end = l;
                } else {
                    end = i + splitLength;
                }
                if (se.quality != null) {
                    SequenceEntry s = new SequenceEntry(se.sequence.substring(i, end), se.quality.substring(i, end));
                    s.header = se.header;
                    list.add(s);
                } else {
                    SequenceEntry s = new SequenceEntry(se.sequence.substring(i, end));
                    s.header = se.header;
                    list.add(s);
                }
            }
        }
        return list;
    }

    public static void saveFile(String path, String sb) {
        try {
            // Create file
            FileWriter fstream = new FileWriter(path);
            try (BufferedWriter out = new BufferedWriter(fstream)) {
                out.write(sb);
            }
        } catch (Exception e) {//Catch exception if any
            System.err.println("Error save file: ");
            System.err.println(path);
        }
    }

    public static void appendFile(String path, String sb) {
        try {
            // Create file
            FileWriter fstream = new FileWriter(path, true);
            try (BufferedWriter out = new BufferedWriter(fstream)) {
                out.write(sb);
            }
        } catch (Exception e) {//Catch exception if any
            System.err.println("Error append file: ");
            System.err.println(path);
            System.err.println(sb);
        }
    }

    /**
     *
     * @param s
     * @return
     */
    public static String reverseComplement(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toUpperCase().toCharArray()) {
            switch (c) {
                case 'A':
                    sb.append("T");
                    break;
                case 'C':
                    sb.append("G");
                    break;
                case 'G':
                    sb.append("C");
                    break;
                case 'T':
                    sb.append("A");
                    break;
                case '-':
                    sb.append("-");
                    break;
            }
        }
        return sb.reverse().toString();
    }

    public static int[] reverse(String s) {
        int[] r = new int[s.length()];
        int i = 0;
        for (char c : s.toUpperCase().toCharArray()) {
            switch (c) {
                case 'A':
                    r[i++] = 0;
                    break;
                case 'C':
                    r[i++] = 1;
                    break;
                case 'G':
                    r[i++] = 2;
                    break;
                case 'T':
                    r[i++] = 3;
                    break;
                case '-':
                    r[i++] = 4;
                    break;
                case 'N':
                    r[i++] = 5;
                    break;
                default:
                    break;
            }
        }
        return r;
    }

    /**
     *
     * @param path
     * @return
     */
    public static boolean isFastaFormat(String path) {
        try {
            FileInputStream fstream = new FileInputStream(path);
            try (DataInputStream in = new DataInputStream(fstream)) {
                BufferedReader br = new BufferedReader(new InputStreamReader(in));
                String strLine;
                while ((strLine = br.readLine()) != null) {
                    if (strLine.startsWith(">")) {
                        return true;
                    } else {
                        return false;
                    }
                }
            }
        } catch (Exception e) {
        }
        return false;
    }

    /**
     *
     * @param path
     * @return
     */
    public static boolean isFastaGlobalMatePairFormat(String path) {
        try {
            FileInputStream fstream = new FileInputStream(path);
            try (DataInputStream in = new DataInputStream(fstream)) {
                BufferedReader br = new BufferedReader(new InputStreamReader(in));
                String strLine;
                while ((strLine = br.readLine()) != null) {
                    if (strLine.startsWith("@")) {
                        return true;
                    } else {
                        return false;
                    }
                }
            }
        } catch (Exception e) {
        }
        return false;
    }

    public static String reverse(int i) {
        switch (i) {
            case 0:
                return "A";
            case 1:
                return "C";
            case 2:
                return "G";
            case 3:
                return "T";
            case 4:
                return "-";
            case 5:
                return "N";
        }
        throw new IllegalAccessError();
    }

    public static void error() {
        System.out.println("    .o oOOOOOOOo                                            OOOo");
        System.out.println("    Ob.OOOOOOOo  OOOo.      oOOo.                      .adOOOOOOO");
        System.out.println("    OboO\"\"\"\"\"\"\"\"\"\"\"\".OOo. .oOOOOOo.    OOOo.oOOOOOo..\"\"\"\"\"\"\"\"\"'OO");
        System.out.println("    OOP.oOOOOOOOOOOO \"POOOOOOOOOOOo.   `\"OOOOOOOOOP,OOOOOOOOOOOB'");
        System.out.println("    `O'OOOO'     `OOOOo\"OOOOOOOOOOO` .adOOOOOOOOO\"oOOO'    `OOOOo");
        System.out.println("    .OOOO'            `OOOOOOOOOOOOOOOOOOOOOOOOOO'            `OO");
        System.out.println("    OOOOO                 '\"OOOOOOOOOOOOOOOO\"`                oOO");
        System.out.println("   oOOOOOba.                .adOOOOOOOOOOba               .adOOOOo.");
        System.out.println("  oOOOOOOOOOOOOOba.    .adOOOOOOOOOO@^OOOOOOOba.     .adOOOOOOOOOOOO");
        System.out.println(" OOOOOOOOOOOOOOOOO.OOOOOOOOOOOOOO\"`  '\"OOOOOOOOOOOOO.OOOOOOOOOOOOOO");
        System.out.println(" \"OOOO\"       \"YOoOOOOMOIONODOO\"`  .   '\"OOROAOPOEOOOoOY\"     \"OOO\"");
        System.out.println("    Y           'OOOOOOOOOOOOOO: .oOOo. :OOOOOOOOOOO?'         :`");
        System.out.println("    :            .oO%OOOOOOOOOOo.OOOOOO.oOOOOOOOOOOOO?         .");
        System.out.println("    .            oOOP\"%OOOOOOOOoOOOOOOO?oOOOOO?OOOO\"OOo");
        System.out.println("                 '%o  OOOO\"%OOOO%\"%OOOOO\"OOOOOO\"OOO':");
        System.out.println("                      `$\"  `OOOO' `O\"Y ' `OOOO'  o             .");
        System.out.println("    .                  .     OP\"          : o     .");
        System.out.println("                              :");
        System.out.println("                              .");
    }
} public final class Alignment {

	/**
	 * Gap character
	 */
	public static final char GAP = '-';

	/**
	 * Default name for sequence #1
	 */
	private static final String SEQUENCE1 = "jaligner_1";

	/**
	 * Default name for sequence #2
	 */
	private static final String SEQUENCE2 = "jaligner_2";

	/**
	 * Scoring matrix
	 */
	private Matrix matrix;

	/**
	 * Gap open cost
	 */
	private float open;

	/**
	 * Gap extend cost
	 */
	private float extend;

	/**
	 * Alignment score
	 */
	private float score;

	/**
	 * Aligned sequence #1
	 */
	private char[] sequence1;

	/**
	 * Name of sequence #1
	 */
	private String name1;

	/**
	 * Alignment start location in sequence #1
	 */
	private int start1;

	/**
	 * Aligned sequence #2
	 */
	private char[] sequence2;

	/**
	 * Name of sequence #2
	 */
	private String name2;

	/**
	 * Alignment start location in sequence #2
	 */
	private int start2;

	/**
	 * Markup line
	 */
	private char[] markupLine;

	/**
	 * Count of identical locations
	 */
	private int identity;

	/**
	 * Count of similar locations
	 */
	private int similarity;

	/**
	 * Count of gap locations
	 */
	private int gaps;

	private Sequence originalSequence1;

	private Sequence originalSequence2;

	/**
	 * Constructor for Alignment
	 */

	public Alignment() {
		super();
	}

	/**
	 * @return Returns the extend.
	 */
	public float getExtend() {
		return extend;
	}

	/**
	 * @param extend
	 *            The extend to set.
	 */
	public void setExtend(float extend) {
		this.extend = extend;
	}

	/**
	 * @return Returns the matrix.
	 */
	public Matrix getMatrix() {
		return matrix;
	}

	/**
	 * @param matrix
	 *            The matrix to set.
	 */
	public void setMatrix(Matrix matrix) {
		this.matrix = matrix;
	}

	/**
	 * @return Returns the name1.
	 */
	public String getName1() {
		return name1 == null || name1.trim().length() == 0 ? SEQUENCE1 : name1;
	}

	/**
	 * @param name1
	 *            The name1 to set.
	 */
	public void setName1(String name1) {
		this.name1 = name1;
	}

	/**
	 * @return Returns the name2.
	 */
	public String getName2() {
		return name2 == null || name2.trim().length() == 0 ? SEQUENCE2 : name2;
	}

	/**
	 * @param name2
	 *            The name2 to set.
	 */
	public void setName2(String name2) {
		this.name2 = name2;
	}

	/**
	 * @return Returns the open.
	 */
	public float getOpen() {
		return open;
	}

	/**
	 * @param open
	 *            The open to set.
	 */
	public void setOpen(float open) {
		this.open = open;
	}

	/**
	 * @return Returns the score.
	 */
	public float getScore() {
		return score;
	}

	/**
	 * @param score
	 *            The score to set.
	 */
	public void setScore(float score) {
		this.score = score;
	}

	/**
	 * Returns the length of the alignment
	 * 
	 * @return Alignment length
	 */
	public int getLength() {
		return this.sequence1.length;
	}

	/**
	 * @return Returns the sequence1.
	 */
	public char[] getSequence1() {
		return sequence1;
	}

	/**
	 * @param sequence1
	 *            The sequence1 to set.
	 */
	public void setSequence1(char[] sequence1) {
		this.sequence1 = sequence1;
	}

	/**
	 * @return Returns the sequence2.
	 */
	public char[] getSequence2() {
		return sequence2;
	}

	/**
	 * @param sequence2
	 *            The sequence2 to set.
	 */
	public void setSequence2(char[] sequence2) {
		this.sequence2 = sequence2;
	}

	/**
	 * @return Returns the start1.
	 */
	public int getStart1() {
		return start1;
	}

	/**
	 * @param start1
	 *            The start1 to set.
	 */
	public void setStart1(int start1) {
		this.start1 = start1;
	}

	/**
	 * @return Returns the start2.
	 */
	public int getStart2() {
		return start2;
	}

	/**
	 * @param start2
	 *            The start2 to set.
	 */
	public void setStart2(int start2) {
		this.start2 = start2;
	}

	/**
	 * @return Returns the gaps.
	 */
	public int getGaps() {
		return gaps;
	}

	/**
	 * @param gaps
	 *            The gaps to set.
	 */
	public void setGaps(int gaps) {
		this.gaps = gaps;
	}

	/**
	 * @return Returns the identity.
	 */
	public int getIdentity() {
		return identity;
	}

	/**
	 * @param identity
	 *            The identity to set.
	 */
	public void setIdentity(int identity) {
		this.identity = identity;
	}

	/**
	 * @return Returns the markupLine.
	 */
	public char[] getMarkupLine() {
		return markupLine;
	}

	/**
	 * @param markupLine
	 *            The markupLine to set.
	 */
	public void setMarkupLine(char[] markupLine) {
		this.markupLine = markupLine;
	}

	/**
	 * @return Returns the similarity.
	 */
	public int getSimilarity() {
		return similarity;
	}

	/**
	 * @param similarity
	 *            The similarity to set.
	 */
	public void setSimilarity(int similarity) {
		this.similarity = similarity;
	}

	/**
	 * Returns a summary for alignment
	 * 
	 * @return {@link String} alignment summary
	 */
	public String getSummary() {
		StringBuffer buffer = new StringBuffer();
		DecimalFormat f1 = new DecimalFormat("0.00");
		DecimalFormat f2 = new DecimalFormat("0.00%");

		int length = getSequence1().length;

		buffer.append("Sequence #1: " + getName1());
		buffer.append(Commons.getLineSeparator());
		buffer.append("Sequence #2: " + getName2());
		buffer.append(Commons.getLineSeparator());
		buffer.append("Length #1: " + getOriginalSequence1().length());
		buffer.append(Commons.getLineSeparator());
		buffer.append("Length #2: " + getOriginalSequence2().length());
		buffer.append(Commons.getLineSeparator());
		buffer.append("Matrix: "
				+ (matrix.getId() == null ? "" : matrix.getId()));
		buffer.append(Commons.getLineSeparator());
		buffer.append("Gap open: " + open);
		buffer.append(Commons.getLineSeparator());
		buffer.append("Gap extend: " + extend);
		buffer.append(Commons.getLineSeparator());
		buffer.append("Length: " + length);
		buffer.append(Commons.getLineSeparator());
		buffer.append("Identity: " + identity + "/" + length + " ("
				+ f2.format(identity / (float) length) + ")");
		buffer.append(Commons.getLineSeparator());
		buffer.append("Similarity: " + similarity + "/" + length + " ("
				+ f2.format(similarity / (float) length) + ")");
		buffer.append(Commons.getLineSeparator());
		buffer.append("Gaps: " + gaps + "/" + length + " ("
				+ f2.format(gaps / (float) length) + ")");
		buffer.append(Commons.getLineSeparator());
		buffer.append("Score: " + f1.format(score));
		buffer.append(Commons.getLineSeparator());

		return buffer.toString();
	}

	/**
	 * Calculate the score of the alignment, not using the score field (the
	 * function only uses sequence1, sequence2, matrix and gap penalties).
	 * 
	 * @return the calculated score (By: Bram Minnaert)
	 */
	public float calculateScore() {
		// The calculated score
		float calcScore = 0;

		// In the previous step there was a gap in the first sequence
		boolean previous1wasGap = false;

		// In the previous step there was a gap in the second sequence
		boolean previous2wasGap = false;

		int start = 0;
		int end = sequence1.length - 1;

		char c1, c2; // the next character
		for (int i = start; i <= end; i++) {
			c1 = sequence1[i];
			c2 = sequence2[i];
			// the next character in the first sequence is a gap
			if (c1 == GAP) {
				if (previous1wasGap) {
					calcScore -= extend;
				} else {
					calcScore -= open;
				}
				previous1wasGap = true;
				previous2wasGap = false;
			}
			// the next character in the second sequence is a gap
			else if (c2 == GAP) {
				if (previous2wasGap) {
					calcScore -= extend;
				} else {
					calcScore -= open;
				}
				previous1wasGap = false;
				previous2wasGap = true;
			}
			// the next characters in boths sequences are not gaps
			else {
				calcScore += matrix.getScore(c1, c2);
				previous1wasGap = false;
				previous2wasGap = false;
			}
		}
		return calcScore;
	}

	/**
	 * Calculate the score of the alignment without the terminal gaps.
	 * 
	 */
	public float getScoreWithNoTerminalGaps() {
		// The calculated score
		float calcScore = 0;

		// In the previous step there was a gap in the first sequence
		boolean previous1wasGap = false;

		// In the previous step there was a gap in the second sequence
		boolean previous2wasGap = false;

		int start = 0;
		int end = sequence1.length - 1;

		if (sequence1[start] == GAP) {
			while (sequence1[start] == GAP) {
				start++;
			}
		} else if (sequence2[start] == GAP) {
			while (sequence2[start] == GAP) {
				start++;
			}
		}

		if (sequence1[end] == GAP) {
			while (sequence1[end] == GAP) {
				end--;
			}
		} else if (sequence2[end] == GAP) {
			while (sequence2[end] == GAP) {
				end--;
			}
		}

		char c1, c2; // the next character
		for (int i = start; i <= end; i++) {
			c1 = sequence1[i];
			c2 = sequence2[i];
			// the next character in the first sequence is a gap
			if (c1 == GAP) {
				if (previous1wasGap) {
					calcScore -= extend;
				} else {
					calcScore -= open;
				}
				previous1wasGap = true;
				previous2wasGap = false;
			}
			// the next character in the second sequence is a gap
			else if (c2 == GAP) {
				if (previous2wasGap) {
					calcScore -= extend;
				} else {
					calcScore -= open;
				}
				previous1wasGap = false;
				previous2wasGap = true;
			}
			// the next characters in boths sequences are not gaps
			else {
				calcScore += matrix.getScore(c1, c2);
				previous1wasGap = false;
				previous2wasGap = false;
			}
		}
		return calcScore;
	}

	/**
	 * Check if the calculated score matches the field score.
	 * 
	 * @return true if equal, else false. (By: Bram Minnaert)
	 */
	public boolean checkScore() {
		if (calculateScore() == score) {
			return true;
		} else {
			return false;
		}
	}

	/**
	 * Returns original {@link Sequence} #1
	 * 
	 * @return original {@link Sequence} #1
	 */
	public Sequence getOriginalSequence1() {
		return originalSequence1;
	}

	/**
	 * 
	 * @param originalSequence1
	 */
	public void setOriginalSequence1(Sequence originalSequence1) {
		this.originalSequence1 = originalSequence1;
	}

	/**
	 * Returns original {@link Sequence} #2
	 * 
	 * @return original {@link Sequence} #2
	 */
	public Sequence getOriginalSequence2() {
		return originalSequence2;
	}

	/**
	 * 
	 * @param originalSequence2
	 */
	public void setOriginalSequence2(Sequence originalSequence2) {
		this.originalSequence2 = originalSequence2;
	}

	/**
	 * Returns the number of gaps of the aligned sequence #1
	 * 
	 * @return the number of gaps of the aligned sequence #1
	 */
	public int getGaps1() {
		int count = 0;
		for (int i = 0, n = sequence1.length; i < n; i++) {
			if (sequence1[i] == Alignment.GAP) {
				count++;
			}
		}
		return count;
	}

	/**
	 * Returns the number of gaps of the aligned sequence #2
	 * 
	 * @return the number of gaps of the aligned sequence #2
	 */
	public int getGaps2() {
		int count = 0;
		for (int i = 0, n = sequence2.length; i < n; i++) {
			if (sequence2[i] == Alignment.GAP) {
				count++;
			}
		}
		return count;
	}

	/**
	 * Adds this alignment to another alignment, the order is important.
	 * 
	 * @param a1
	 *            The 1st alignment
	 * @param a2
	 *            The 2nd alignment
	 * @return the sum of two alignment
	 */
	public static Alignment add(Alignment a1, Alignment a2) {

		if (a1 == null) {
			if (a2 == null) {
				return null;
			} else {
				return copy(a2);
			}
		} else {
			if (a2 == null) {
				return copy(a1);
			} else {
				Alignment sum = new Alignment();

				StringBuffer buffer = new StringBuffer();

				buffer.append(a1.getOriginalSequence1());
				buffer.append(a2.getOriginalSequence1());

				sum.setOriginalSequence1(new Sequence(buffer.toString()));

				buffer = new StringBuffer();

				buffer.append(a1.getOriginalSequence2());
				buffer.append(a2.getOriginalSequence2());

				sum.setOriginalSequence2(new Sequence(buffer.toString()));

				buffer = new StringBuffer();

				buffer.append(a1.getSequence1());
				buffer.append(a2.getSequence1());

				sum.setSequence1(buffer.toString().toCharArray());

				buffer = new StringBuffer();

				buffer.append(a1.getSequence2());
				buffer.append(a2.getSequence2());

				sum.setSequence2(buffer.toString().toCharArray());

				buffer = new StringBuffer();

				buffer.append(a1.getMarkupLine());
				buffer.append(a2.getMarkupLine());

				sum.setMarkupLine(buffer.toString().toCharArray());

				sum.setScore(a1.getScore() + a2.getScore());
				sum.setGaps(a1.getGaps() + a2.getGaps());

				sum.setStart1(a1.getStart1());
				sum.setStart2(a1.getStart2());
				sum.setExtend(a1.getExtend());
				sum.setOpen(a1.getOpen());
				sum.setMatrix(a1.getMatrix());

				return sum;
			}
		}
	}

	/**
	 * Copies an alignment to another alignment.
	 * 
	 * @param alignment
	 *            Alignment
	 */
	public static Alignment copy(Alignment alignment) {

		Alignment copy = new Alignment();

		copy.setSequence1(alignment.getSequence1());
		copy.setSequence2(alignment.getSequence2());
		copy.setMarkupLine(alignment.getMarkupLine());
		copy.setScore(alignment.getScore());
		copy.setGaps(alignment.getGaps());
		copy.setStart1(alignment.getStart1());
		copy.setStart2(alignment.getStart2());
		copy.setExtend(alignment.getExtend());
		copy.setOpen(alignment.getOpen());
		copy.setMatrix(alignment.getMatrix());
		copy.setOriginalSequence1(alignment.getOriginalSequence1());
		copy.setOriginalSequence2(alignment.getOriginalSequence2());

		return copy;
	}
} public class Sequence implements Serializable {
	/**
	 * 
	 */
	private static final long serialVersionUID = 3256721801357898297L;

	/**
	 * Sequence type nucleic.
	 */
	public static final int NUCLEIC = 0;

	/**
	 * Sequence type protein.
	 */
	public static final int PROTEIN = 1;

	/**
	 * Sequence
	 */
	private String sequence;

	/**
	 * Sequence id.
	 */
	private String id = null;

	/**
	 * Sequence description.
	 */
	private String description = null;

	/**
	 * Sequence type.
	 */
	private int type = PROTEIN;

	/**
	 * Constructor
	 */
	public Sequence() {
		super();
	}

	/**
	 * Constructor
	 * 
	 * @param sequence
	 */
	public Sequence(String sequence) {
		super();
		this.sequence = sequence;
	}
	
	/**
	 * Constructor
	 * 
	 * @param name
	 * @param sequence
	 */
	public Sequence(String name, char[] sequence) {
		super();
		this.id = name;
		this.sequence = new String(sequence);
	}

	/**
	 * Constructor
	 * 
	 * @param name
	 * @param sequence
	 */
	public Sequence(String name, String sequence) {
		super();
		this.id = name;
		this.sequence = sequence;
	}

	/**
	 * Constructor
	 * 
	 * @param sequence
	 * @param id
	 * @param description
	 * @param type
	 */
	public Sequence(String sequence, String id, String description, int type) {
		super();
		this.sequence = sequence;
		this.id = id;
		this.description = description;
		this.type = type;
	}

	/**
	 * Returns the sequence string
	 * 
	 * @return Returns the sequence
	 */
	public String getSequence() {
		return sequence;
	}

	/**
	 * Sets the sequence string
	 * 
	 * @param sequence
	 *            The sequence to set
	 */
	public void setSequence(String sequence) {
		this.sequence = sequence;
	}

	/**
	 * Returns the sequence id
	 * 
	 * @return Returns the id
	 */
	public String getId() {
		return id;
	}

	/**
	 * Sets the sequence id
	 * 
	 * @param id
	 *            The id to set
	 */
	public void setId(String id) {
		this.id = id;
	}

	/**
	 * Returns the sequence description
	 * 
	 * @return Returns the description
	 */
	public String getDescription() {
		return description;
	}

	/**
	 * Sets the sequence description
	 * 
	 * @param description
	 *            The description to set
	 */
	public void setDescription(String description) {
		this.description = description;
	}

	/**
	 * Returns the sequence type (nucleic or protein)
	 * 
	 * @return Returns the type
	 */
	public int getType() {
		return type;
	}

	/**
	 * Sets the sequence type (nucleic or protein)
	 * 
	 * @param type
	 *            The type to set
	 */
	public void setType(int type) {
		this.type = type;
	}

	/**
	 * Returns the length of the sequence
	 * 
	 * @return sequence length
	 */
	public int length() {
		return this.sequence.length();
	}

	/**
	 * Returns a subsequence
	 * 
	 * @param index
	 *            start index
	 * @param length
	 *            length of subsequence
	 * @return subsequence
	 */
	public String subsequence(int index, int length) {
		return this.sequence.substring(index, index + length);
	}

	/**
	 * Returns the acid at specific location in the sequence
	 * 
	 * @param index
	 * @return acid at index
	 */
	public char acidAt(int index) {
		return this.sequence.charAt(index);
	}

	/**
	 * Returns the sequence as an array of characters.
	 * 
	 * @return array of chars.
	 */
	public char[] toArray() {
		return this.sequence.toCharArray();
	}
    
    /**
     * Returns the sequence id and the sequence string
     * 
     * @return Returns the sequence id and the sequence string
     */
    public String toString() {
        return id + Commons.TAB + sequence;
    }
} public final class SmithWatermanGotoh {

    /**
     * Hidden constructor
     */
    private SmithWatermanGotoh() {
        super();
    }

    /**
     * Aligns two sequences by Smith-Waterman (local)
     *
     * @param s1 sequene #1 ({@link Sequence})
     * @param s2 sequene #2 ({@link Sequence})
     * @param matrix scoring matrix ({@link Matrix})
     * @param o open gap penalty
     * @param e extend gap penalty
     * @return alignment object contains the two aligned sequences, the
     * alignment score and alignment statistics
     * @see Sequence
     * @see Matrix
     */
    public static Alignment align(Sequence s1, Sequence s2, Matrix matrix,
            float o, float e) {
        float[][] scores = matrix.getScores();

        int m = s1.length() + 1;
        int n = s2.length() + 1;

        byte[] pointers = new byte[m * n];

        // Initializes the boundaries of the traceback matrix to STOP.
        for (int i = 0, k = 0; i < m; i++, k += n) {
            pointers[k] = Directions.STOP;
        }
        for (int j = 1; j < n; j++) {
            pointers[j] = Directions.STOP;
        }

        short[] sizesOfVerticalGaps = new short[m * n];
        short[] sizesOfHorizontalGaps = new short[m * n];
        for (int i = 0, k = 0; i < m; i++, k += n) {
            for (int j = 0; j < n; j++) {
                sizesOfVerticalGaps[k + j] = sizesOfHorizontalGaps[k + j] = 1;
            }
        }

        Cell cell = SmithWatermanGotoh.construct(s1, s2, scores, o, e,
                pointers, sizesOfVerticalGaps, sizesOfHorizontalGaps);
        Alignment alignment = SmithWatermanGotoh.traceback(s1, s2, matrix,
                pointers, cell, sizesOfVerticalGaps, sizesOfHorizontalGaps);
        alignment.setOriginalSequence1(s1);
        alignment.setOriginalSequence2(s2);
        alignment.setMatrix(matrix);
        alignment.setOpen(o);
        alignment.setExtend(e);
        if (s1.getId() != null) {
            alignment.setName1(s1.getId());
        }
        if (s2.getId() != null) {
            alignment.setName2(s2.getId());
        }
        return alignment;
    }

    /**
     * Constructs directions matrix for the traceback
     *
     * @param s1 sequence #1
     * @param s2 sequence #2
     * @param matrix scoring matrix
     * @param o open gap penalty
     * @param e extend gap penalty
     * @return The cell where the traceback starts.
     */
    private static Cell construct(Sequence s1, Sequence s2, float[][] matrix,
            float o, float e, byte[] pointers, short[] sizesOfVerticalGaps,
            short[] sizesOfHorizontalGaps) {
        long start = System.currentTimeMillis();

        char[] a1 = s1.toArray();
        char[] a2 = s2.toArray();

        int m = s1.length() + 1;
        int n = s2.length() + 1;

        float f; // score of alignment x1...xi to y1...yi if xi aligns to yi
        float[] g = new float[n]; // score if xi aligns to a gap after yi
        float h; // score if yi aligns to a gap after xi
        float[] v = new float[n]; // best score of alignment x1...xi to
        // y1...yi
        float vDiagonal;

        g[0] = Float.NEGATIVE_INFINITY;
        h = Float.NEGATIVE_INFINITY;
        v[0] = 0;

        for (int j = 1; j < n; j++) {
            g[j] = Float.NEGATIVE_INFINITY;
            v[j] = 0;
        }

        float similarityScore, g1, g2, h1, h2;

        Cell cell = new Cell();

        for (int i = 1, k = n; i < m; i++, k += n) {
            h = Float.NEGATIVE_INFINITY;
            vDiagonal = v[0];
            for (int j = 1, l = k + 1; j < n; j++, l++) {
                similarityScore = matrix[a1[i - 1]][a2[j - 1]];

                // Fill the matrices
                f = vDiagonal + similarityScore;

                g1 = g[j] - e;
                g2 = v[j] - o;
                if (g1 > g2) {
                    g[j] = g1;
                    sizesOfVerticalGaps[l] = (short) (sizesOfVerticalGaps[l - n] + 1);
                } else {
                    g[j] = g2;
                }

                h1 = h - e;
                h2 = v[j - 1] - o;
                if (h1 > h2) {
                    h = h1;
                    sizesOfHorizontalGaps[l] = (short) (sizesOfHorizontalGaps[l - 1] + 1);
                } else {
                    h = h2;
                }

                vDiagonal = v[j];
                v[j] = maximum(f, g[j], h, 0);

                // Determine the traceback direction
                if (v[j] == 0) {
                    pointers[l] = Directions.STOP;
                } else if (v[j] == f) {
                    pointers[l] = Directions.DIAGONAL;
                } else if (v[j] == g[j]) {
                    pointers[l] = Directions.UP;
                } else {
                    pointers[l] = Directions.LEFT;
                }

                // Set the traceback start at the current cell i, j and score
                if (v[j] > cell.getScore()) {
                    cell.set(i, j, v[j]);
                }
            }
        }
        return cell;
    }

    /**
     * Returns the alignment of two sequences based on the passed array of
     * pointers
     *
     * @param s1 sequence #1
     * @param s2 sequence #2
     * @param m scoring matrix
     * @param cell The cell where the traceback starts.
     * @return {@link Alignment}with the two aligned sequences and alignment
     * score.
     * @see Cell
     * @see Alignment
     */
    private static Alignment traceback(Sequence s1, Sequence s2, Matrix m,
            byte[] pointers, Cell cell, short[] sizesOfVerticalGaps,
            short[] sizesOfHorizontalGaps) {

        char[] a1 = s1.toArray();
        char[] a2 = s2.toArray();

        float[][] scores = m.getScores();

        int n = s2.length() + 1;

        Alignment alignment = new Alignment();
        alignment.setScore(cell.getScore());

        int maxlen = s1.length() + s2.length(); // maximum length after the
        // aligned sequences

        char[] reversed1 = new char[maxlen]; // reversed sequence #1
        char[] reversed2 = new char[maxlen]; // reversed sequence #2
        char[] reversed3 = new char[maxlen]; // reversed markup

        int len1 = 0; // length of sequence #1 after alignment
        int len2 = 0; // length of sequence #2 after alignment
        int len3 = 0; // length of the markup line

        int identity = 0; // count of identitcal pairs
        int similarity = 0; // count of similar pairs
        int gaps = 0; // count of gaps

        char c1, c2;

        int i = cell.getRow(); // traceback start row
        int j = cell.getCol(); // traceback start col
        int k = i * n;

        boolean stillGoing = true; // traceback flag: true -> continue & false
        // -> stop

        while (stillGoing) {
            switch (pointers[k + j]) {
                case Directions.UP:
                    for (int l = 0, len = sizesOfVerticalGaps[k + j]; l < len; l++) {
                        reversed1[len1++] = a1[--i];
                        reversed2[len2++] = Alignment.GAP;
                        reversed3[len3++] = Markups.GAP;
                        k -= n;
                        gaps++;
                    }
                    break;
                case Directions.DIAGONAL:
                    c1 = a1[--i];
                    c2 = a2[--j];
                    k -= n;
                    reversed1[len1++] = c1;
                    reversed2[len2++] = c2;
                    if (c1 == c2) {
                        reversed3[len3++] = Markups.IDENTITY;
                        identity++;
                        similarity++;
                    } else if (scores[c1][c2] > 0) {
                        reversed3[len3++] = Markups.SIMILARITY;
                        similarity++;
                    } else {
                        reversed3[len3++] = Markups.MISMATCH;
                    }
                    break;
                case Directions.LEFT:
                    for (int l = 0, len = sizesOfHorizontalGaps[k + j]; l < len; l++) {
                        reversed1[len1++] = Alignment.GAP;
                        reversed2[len2++] = a2[--j];
                        reversed3[len3++] = Markups.GAP;
                        gaps++;
                    }
                    break;
                case Directions.STOP:
                    stillGoing = false;
            }
        }

        alignment.setSequence1(reverse(reversed1, len1));
        alignment.setStart1(i);
        alignment.setSequence2(reverse(reversed2, len2));
        alignment.setStart2(j);
        alignment.setMarkupLine(reverse(reversed3, len3));
        alignment.setIdentity(identity);
        alignment.setGaps(gaps);
        alignment.setSimilarity(similarity);

        return alignment;
    }

    /**
     * Returns the maximum of 4 float numbers.
     *
     * @param a float #1
     * @param b float #2
     * @param c float #3
     * @param d float #4
     * @return The maximum of a, b, c and d.
     */
    private static float maximum(float a, float b, float c, float d) {
        if (a > b) {
            if (a > c) {
                return a > d ? a : d;
            } else {
                return c > d ? c : d;
            }
        } else if (b > c) {
            return b > d ? b : d;
        } else {
            return c > d ? c : d;
        }
    }

    /**
     * Reverses an array of chars
     *
     * @param a
     * @param len
     * @return the input array of char reserved
     */
    private static char[] reverse(char[] a, int len) {
        char[] b = new char[len];
        for (int i = len - 1, j = 0; i >= 0; i--, j++) {
            b[j] = a[i];
        }
        return b;
    }
} public class Matrix implements Serializable {
	/**
	 * 
	 */
	private static final long serialVersionUID = 3833742170619524400L;
	
	/**
	 * The size of the scoring matrix. It is the number of the characters in the
	 * ASCII table. It is more than the 20 amino acids just to save the
	 * processing time of the mapping.
	 */
	public static final int SIZE = 127;

	/**
	 * Matrix id (or name)
	 */
	private final String id;

	/**
	 * Scores
	 */
	private final float[][] scores;

	public Matrix(String id, float[][] scores) {
		this.id = id;
		this.scores = scores;
	}

	/**
	 * @return Returns the id.
	 */
	public String getId() {
		return this.id;
	}

	/**
	 * @return Returns the scores.
	 */
	public float[][] getScores() {
		return this.scores;
	}

	/**
	 * 
	 * @param a
	 * @param b
	 * @return score
	 */
	public float getScore(char a, char b) {
		return this.scores[a][b];
	}
}
import java.util.concurrent.Callable;
import ch.ethz.bsse.indelfixer.stored.GapCosts;
import ch.ethz.bsse.indelfixer.stored.Genome;
import ch.ethz.bsse.indelfixer.stored.Globals;
import ch.ethz.bsse.indelfixer.stored.Kmer;
import ch.ethz.bsse.indelfixer.stored.Read;
import ch.ethz.bsse.indelfixer.stored.SequenceEntry;
import ch.ethz.bsse.indelfixer.utils.StatusUpdate;
import ch.ethz.bsse.indelfixer.utils.Utils;
import jaligner.Alignment;
import jaligner.Sequence;
import jaligner.SmithWatermanGotoh;
import jaligner.matrix.Matrix;
import java.util.LinkedList;
import java.util.List;

/**
 * Copyright (c) 2011-2013 Armin Töpfer
 *
 * This file is part of InDelFixer.
 *
 * InDelFixer is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or any later version.
 *
 * InDelFixer is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along with
 * InDelFixer. If not, see <http://www.gnu.org/licenses/>.
 */
package ch.ethz.bsse.indelfixer.minimal.processing.parallel;


/**
 * @author Armin Töpfer (armin.toepfer [at] gmail.com)
 */
public class FutureSequence implements Callable<List<Object>> {

    private final List<SequenceEntry> watsonEntries;
    private final Genome[] genome;
    private final Matrix matrix;

    public FutureSequence(List<SequenceEntry> watson) {
        this.watsonEntries = watson;
        this.genome = Globals.GENOMES;
        this.matrix = Globals.MATRIX;
    }

    @Override
    public List<Object> call() {
        List<Object> output = new LinkedList<>();
        for (SequenceEntry watsonEntry : watsonEntries) {
            if (watsonEntry != null) {

                Read watsonRead = map(createRead(watsonEntry, false));
