Java Regex para el rompecabezas del genoma

Question

Se me asignó un problema para encontrar genes cuando recibía una serie de letras A, C, G o T, todas seguidas, como ATGCTCTCTTGATTTTTTTATGTGTAGCCATGCACACACACACATAAGA. Un gen se inicia con ATG y termina con TAA, TAG o TGA (el gen excluye ambos extremos). El gen consta de trillizos de letras, por lo que su longitud es un múltiplo de tres, y ninguno de esos trillizos puede ser los trillizos de inicio/final enumerados anteriormente. Entonces, para la cadena de arriba, los genes que contiene son CTCTCT y CACACACACACA. Y, de hecho, mi expresión regular funciona para esa cadena en particular. Esto es lo que tengo hasta ahora (y estoy bastante contento con mi mismo que llegué hasta aquí):

(?<=ATG)(([ACGT]{3}(?<!ATG))+?)(?=TAG|TAA|TGA) 

Sin embargo, si hay un ATG y uso final del triplete dentro de otro resultado, y no alineada con los trillizos de ese resultado, falla. Por ejemplo:

Results for TCGAATGTTGCTTATTGTTTTGAATGGGGTAGGATGACCTGCTAATTGGGGGGGGGG : 
TTGCTTATTGTTTTGAATGGGGTAGGA 
ACCTGC 

Se debe encontrar también una GGG pero no lo hace: TTGCTTATTGTTTTGA (ATG | GGG | TAG) GA

Soy nuevo en regex en general y un poco atascado ... sólo una pequeña sugerencia sería increíble!

Answer 1

He aquí una posible expresión regular:

(?=(ATG((?!ATG)[ATGC]{3})*(TAA|TAG|TGA))) 

Una pequeña prueba de plataforma:

public class Main { 
    public static void main(String[]args) { 
     String source = "TCGAATGTTGCTTATTGTTTTGAATGGGGTAGGATGACCTGCTAATTGGGGGGGGGGATGATGTAG"; 
     Matcher m = Pattern.compile("(?=(ATG((?!ATG)[ATGC]{3})*(TAA|TAG|TGA)))").matcher(source); 
     System.out.println("source : "+source+"\nmatches:"); 
     while(m.find()) { 
      System.out.print("   "); 
      for(int i = 0; i < m.start(); i++) { 
       System.out.print(" "); 
      } 
      System.out.println(m.group(1)); 
     } 
    } 
} 

que produce:

source : TCGAATGTTGCTTATTGTTTTGAATGGGGTAGGATGACCTGCTAATTGGGGGGGGGGATGATGTAG 
matches: 
      ATGTTGCTTATTGTTTTGAATGGGGTAGGATGACCTGCTAATTGGGGGGGGGGATGA 
           ATGGGGTAG 
              ATGACCTGCTAA 
                    ATGTAG 

Answer 2

El problema es que la expresión regular consume los caracteres que coincide y luego no se vuelven a usar.

Puede resolver esto usando una coincidencia de ancho cero (en cuyo caso solo obtiene el índice de la coincidencia, no los caracteres que coinciden).

Alternativamente, puede utilizar tres expresiones regulares similares, cada uno usando un offset diferente:

(?=(.{3})+$)(?<=ATG)(([ACGT]{3}(?<!ATG))+?)(?=TAG|TAA|TGA) 
(?=(.{3})+.$)(?<=ATG)(([ACGT]{3}(?<!ATG))+?)(?=TAG|TAA|TGA) 
(?=(.{3})+..$)(?<=ATG)(([ACGT]{3}(?<!ATG))+?)(?=TAG|TAA|TGA) 

También puede ser que desee considerar el uso de un enfoque diferente que no implica expresiones regulares como la expresión regular anterior sería Sé lento.

Answer 3

El problema con este tipo de cosas es que puedes construir lentamente una expresión regular, regla por regla, hasta que tengas algo que funcione.

Luego cambian sus requisitos y debe comenzar de nuevo, porque para los simples mortales es casi imposible realizar ingeniería inversa inversa compleja.

Personalmente, preferiría hacerlo de la manera "pasada de moda" - utilizar la manipulación de cadenas. Cada etapa se puede comentar fácilmente, y si hay un ligero cambio en los requisitos, puede modificar una etapa en particular.

Answer 4

Quizás debería probar con otros métodos como trabajar con índices. Algo como:

public static final String genome="ATGCTCTCTTGATTTTTTTATGTGTAGCCATGCACACACACACATAAGA"; 
public static final String start_codon = "ATG"; 
public final static String[] end_codons = {"TAA","TAG","TGA"}; 

public static void main(String[] args) { 
    List<Integer>start_indexes = new ArrayList<Integer>(); 
    int curIndex = genome.indexOf(start_codon); 
     while(curIndex!=-1){ 
      start_indexes.add(curIndex); 
      curIndex = genome.indexOf(start_codon,curIndex+1); 
     } 
} 

haga lo mismo para otros codones, y vea si los índices coinciden con la regla de triplete. Por cierto, ¿estás seguro de que un gen excluye un codón de inicio? (Algunos ATG se puede encontrar en un gen)