Aligning DNA Sequences

Mutating the NBA

Professor Farnsworth has once again descended into a moronic battle of science and wits against his archnemesis Professor Wernstrom, though this time it is a battle of honour on the basketball court. TheProfessor has decided to create a team of undefeatable mutants very unlike but not quite dissimilar to theones he used to fight the Globetrotters to defend earths dignity. His diabolical scheme is to use the DNAof the best NBA players to manufacture the perfect team. But he wants to use players who have a variedexpertise to make sure that each mutant is the best possible one for the team composition.
Help the Professor so that he is best able to analyze the sequence of any two players.
Input Format
The input consists of two lines, where each sequence and are the DNA sequence of the players.
Constraints
Output Format
First output the optimal score of aligning the two sequences. Assume that scoring matrix adds to thescore for a match and for a mismatch.
Then output an optimal alignment of the two sequences.
Sample Input 0
GAT
GAT
Sample Output 0
6G
AT
GAT
Sample Input 1
CAG
AAG
Sample Output 1
3C
AG
AAG
Sample Input 2
ACGCCG
ACCACG
Sample Output 2
8A
CGC_CG
AC_CACG

Solution

importjava.io.BufferedReader;

importjava.io.IOException;

importjava.io.InputStreamReader;

importjava.util.HashMap;

public class Solution {

public static HashMap<String, Answer>prevResults = new HashMap<String, Answer>();

public static Answer recursion(String lineone, String linetwo) {

String prevResultKey = lineone + “?” + linetwo;

if (prevResults.containsKey(prevResultKey)) {

returnprevResults.get(prevResultKey);

}

if (lineone.equals(“”) || linetwo.equals(“”)) {

if(lineone.equals(“”)){

Answer newanswer = new Answer();

for(int i = 0; i <linetwo.length(); i++){

newanswer.lineone+=”_”;

}

newanswer.linetwo += linetwo;

newanswer.score = -linetwo.length();

prevResults.put(newanswer.key(), newanswer.clone());

returnnewanswer;

}

else if(linetwo.equals(“”)){

Answer newanswer = new Answer();

for(int i = 0; i <lineone.length(); i++){

newanswer.linetwo+=”_”;

}

newanswer.lineone += lineone;

newanswer.score = -lineone.length();

prevResults.put(newanswer.key(), newanswer.clone());

returnnewanswer;

}

} else {

Answer joinFirstLetterScore = recursion(lineone.substring(1, lineone.length()),

linetwo.substring(1, linetwo.length()));

Answer removeFirstLineLetterScore = recursion(lineone.substring(1, lineone.length()), linetwo);

Answer removeSecondLineLetterScore = recursion(lineone, linetwo.substring(1, linetwo.length()));

removeFirstLineLetterScore.score -= 1;

removeSecondLineLetterScore.score -= 1;

if (lineone.substring(0, 1).equals(linetwo.substring(0, 1))) {

joinFirstLetterScore.score += 2;

}

else {

joinFirstLetterScore.score -= 1;

}

if (removeFirstLineLetterScore.score>= joinFirstLetterScore.score

&&removeFirstLineLetterScore.score>= removeSecondLineLetterScore.score) {

Answer answerone = new Answer();

answerone.lineone = lineone.substring(0, 1);

answerone.linetwo = (“_”);

answerone.score = removeFirstLineLetterScore.score;

answerone.lineone += removeFirstLineLetterScore.lineone;

answerone.linetwo += removeFirstLineLetterScore.linetwo;

prevResults.put(answerone.key(), answerone.clone());

returnanswerone.clone();

}

if (removeSecondLineLetterScore.score>= joinFirstLetterScore.score

&&removeSecondLineLetterScore.score>= removeFirstLineLetterScore.score) {

Answer answertwo = new Answer();

answertwo.linetwo = linetwo.substring(0, 1);

answertwo.lineone = (“_”);

answertwo.score = removeSecondLineLetterScore.score;

answertwo.lineone += removeSecondLineLetterScore.lineone;

answertwo.linetwo += removeSecondLineLetterScore.linetwo;

prevResults.put(answertwo.key(), answertwo.clone());

returnanswertwo.clone();

}

if (joinFirstLetterScore.score>= removeFirstLineLetterScore.score

&&joinFirstLetterScore.score>= removeSecondLineLetterScore.score) {

Answer answerthree = new Answer();

answerthree.lineone = lineone.substring(0, 1);

answerthree.linetwo = linetwo.substring(0, 1);

answerthree.score = joinFirstLetterScore.score;

answerthree.lineone += joinFirstLetterScore.lineone;

answerthree.linetwo += joinFirstLetterScore.linetwo;

prevResults.put(answerthree.key(), answerthree.clone());

returnanswerthree.clone();

}

}

return null;

}

public static void main(String[] args) throws NumberFormatException, IOException {

BufferedReader b = new BufferedReader(new InputStreamReader(System.in));

String lineone = b.readLine();

String linetwo = b.readLine();

Answer answer = new Answer();

answer = (recursion(lineone, linetwo));

//answer.Score();

answer.Print();

}

}

class Answer {

String lineone, linetwo;

int score;

public Answer() {

lineone = “”;

linetwo = “”;

score = 0;

}

public Answer(String l1, String l2, int s) {

lineone = l1;

linetwo = l2;

score = s;

}

public void Print(){

System.out.println(score);

System.out.println(lineone);

System.out.println(linetwo);

}

public String key() {

returnlineone + “?” + linetwo;

}

public Answer clone() {

return new Answer(lineone, linetwo, score);

}

/**   public void Score(){

inttempscore = 0;

for(int i = 0; i <lineone.length(); i++){

if(lineone.substring(i, 1+i).equals(linetwo.substring(i, 1+i))){

tempscore+=2;

}

else{

tempscore-=1;

}

score = tempscore;

}

}*/

}