Busca de strings diferentes usando IndexOf em sequencias de DNA

Oi Roberto Andrade,

Não conheço jeito trivial de fazer isso, talvez neste framework que esteja usando haja algo para este tipo de tarefa.

Para todo caso, bolei um algoritmo que faz esta tarefa.

Meu algoritmo é baseado no conceito de distância de Hamming. http://pt.wikipedia.org/wiki/Distância_de_Hamming

Bom, segue o algoritmo:

public class ComparationTest {

    public static void main(String[] args) {

	   String x = "ACCCCCCCCCCCCCCCGTGTGAGTGTTTTTTTTTT";

	   String y = "AGTCTT";
	
	   boolean t = true;

	   int index = 0;

	   String result = "Não fui mexido.";

	   int yLen = y.length();

	   while(t) {
	       // Nesta linha cortamos a string e um pedaço menor
	       String chomp = chomp(yLen, x, index);
	       int count = hamming(chomp, y);

	       if (count == 1 || count == 0) { // Interrompirá se a distancia de hamming
		                               // indicar que as strings são iguais ou um character diferente.
		   t = false;
		   result = chomp;

	        } else if (count == -1) {

		   t = false; // Não temos mais substrings com tamanho suficiente para comparar.

	       }

	       index++;
	   }

	   System.out.println(result); // O resultado será AGTGTT.
    }

    public static String chomp(int yLen, String x, int ini) {
	   if(x.length() < yLen){ return ""; }
	   return x.substring(ini, ini + yLen);
    }

    public static int hamming(String chomp, String y) {
	   // Hamming só funciona com strings do mesmo tamanho.
	   int chompLen = chomp.length();
	   if(chompLen != y.length()) {
	       return -1;
	   }

	   int distancia = 0;
	   for(int k=0; k < chompLen; k++) {
	       if (chomp.charAt(k) != y.charAt(k)) {
		      distancia++;
	       } 
	   }
	   return distancia;
    }
}

Se calculei certo, este algoritmo é da seguinte ordem: O(n^2).

Problema interessante este, vc trabalha com bioinformática?

Até mais.

Obrigado csr_ pelo código. Será muito útil, pois eu posso controlar a variável distancia e obter strings com 1, 2 ou 3 caracteres incorretos.
Acho que funcionará bem, pois trabalho com genomas pequenos e dividi-los no tamanho da string procurada não consumirá tanta memória.

Procurei na doc Java por alguma função que pudesse aumentar a eficiência, mas pelo visto não há.

Abcs.

É claro - para começar, evite usar Strings java, porque elas gastam 2 bytes por caracter - isso é característico da linguagem. Em vez disso, tente usar sequencias de bytes mesmo.

Outra coisa, você precisa começar a ler alguns papers sobre algoritmos melhores que indexOf (que obviamente não vai dar os resultados desejados).

Você pode procurar no Google com as palavras chave: dna sequences pattern matching

Um exemplo: http://www.ijcaonline.org/volume17/number8/pxc3872862.pdf - pode ser que este artigo não lhe dê o algoritmo que você precisa, mas possa lhe informar sobre outros algoritmos que possam ser melhores no seu caso.

Talvez seja necessário abandonar o Java e usar a linguagem que os autores dos papers que você for achar usaram - talvez C++ ou ainda outra linguagem.

Olá entanglemnt,

Valeu pelas infos. Na verdade, eu trabalho com PERL, mas com este software que estou desenvolvendo é necessário uma interface gráfica melhor.

Abrcs.