Java Regex per il genoma puzzle

Question

Mi è stato assegnato un problema per trovare i geni quando si assegnava una stringa delle lettere A, C, G o T tutto in una riga, come ATGCTCTCTTGATTTTTTTATGTGTAGCCATGCACACACACACATAAGA. Un gene viene avviato con ATG e termina con TAA, TAG o TGA (il gene esclude entrambi gli endpoint). Il gene consiste di terzine di lettere, quindi la sua lunghezza è un multiplo di tre e nessuna di queste terzine può essere la tripletta di inizio/fine sopra elencata. Quindi, per la stringa sopra i geni in esso ci sono CTCTCT e CACACACACACA. E in effetti la mia regex funziona per quella stringa particolare. Ecco quello che ho finora (e sono abbastanza felice con me stesso che ho ottenuto fino a questo punto):

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

Tuttavia, se v'è un ATG e fine tripletta all'interno di un altro risultato, e non allineato con le triplette di quel risultato, fallisce. Per esempio:

Results for TCGAATGTTGCTTATTGTTTTGAATGGGGTAGGATGACCTGCTAATTGGGGGGGGGG : 
TTGCTTATTGTTTTGAATGGGGTAGGA 
ACCTGC 

Si dovrebbe trovare anche una GGG, ma non lo fa: TTGCTTATTGTTTTGA (ATG | GGG | TAG) GA

Sono nuovo di regex in generale, e un po 'bloccato ... basta un piccolo suggerimento sarebbe fantastico!

Answer 1

Ecco una possibile espressione regolare:

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

un piccolo test-rig:

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)); 
     } 
    } 
} 

che produce:

source : TCGAATGTTGCTTATTGTTTTGAATGGGGTAGGATGACCTGCTAATTGGGGGGGGGGATGATGTAG 
matches: 
      ATGTTGCTTATTGTTTTGAATGGGGTAGGATGACCTGCTAATTGGGGGGGGGGATGA 
           ATGGGGTAG 
              ATGACCTGCTAA 
                    ATGTAG 

Answer 2

Il problema è che l'espressione regolare consuma i caratteri che corrisponde e quindi non vengono più utilizzati.

È possibile risolvere questo problema utilizzando una corrispondenza di larghezza zero (nel qual caso si ottiene solo l'indice della corrispondenza, non i caratteri corrispondenti).

In alternativa è possibile utilizzare tre espressioni regolari simili, ma ognuno con un diverso offset:

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

si potrebbe anche voler considerare l'utilizzo di un approccio diverso che non coinvolge le espressioni regolari come sopra espressione regolare sarebbe essere lento

Answer 3

Il problema con cose come questa è che puoi lentamente costruire una regex, regola per regola, finché non hai qualcosa che funziona.

Poi le tue esigenze cambiano e devi ricominciare tutto da capo, perché è quasi impossibile per i semplici mortali riuscire a decodificare facilmente una regex complessa.

Personalmente, preferirei farlo in modo "vecchio stile" - utilizzare la manipolazione delle stringhe. Ogni fase può essere facilmente commentata, e se c'è un leggero cambiamento nei requisiti puoi semplicemente modificare un particolare livello.

Answer 4

Forse dovresti provare con altri metodi come lavorare con gli indici. Qualcosa del tipo:

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); 
     } 
} 

fare lo stesso per altri codoni e vedere se gli indici corrispondono alla regola della terzina. A proposito, sei sicuro che un gene escluda un codone di partenza? (Alcuni ATG può essere trovato in un gene)