Java Regex для головоломки генома

Question

Мне была назначена проблема поиска генов при задании строки букв A, C, G или T в целом, например, ATGCTCTCTTGATTTTTTGGGGGTAGTATTACTACTACTAGTAGTAGTAGTATTTTTTGTGTAGCCATGCACACACACACATAAGA. Ген запускается с ATG и заканчивается либо TAA, TAG, либо TGA (ген исключает обе конечные точки). Ген состоит из триплетов букв, поэтому его длина кратна трем, и ни один из этих триплетов не может быть триплетами начала/конца, перечисленными выше. Итак, для строки выше генов в ней находятся CTCTCT и CACACACACACA. И на самом деле мое регулярное выражение работает для этой конкретной строки. Вот то, что я до сих пор (и я очень доволен собой, что я получил это далеко):

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

Однако, если есть ATG и конечный триплет внутри другого результата и не выровнены с тройни этого результата он терпит неудачу. Например:

Results for TCGAATGTTGCTTATTGTTTTGAATGGGGTAGGATGACCTGCTAATTGGGGGGGGGG : 
TTGCTTATTGTTTTGAATGGGGTAGGA 
ACCTGC 

Он должен найти также GGG, но не делает: TTGCTTATTGTTTTGA (ATG | GGG | TAG) GA

Я новичок в Regex в целом и немного застрял ... просто маленький намек был бы потрясающим!

Answer 1

Вот возможный регулярное выражение:

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

Небольшой тест-установка:

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

, который производит:

source : TCGAATGTTGCTTATTGTTTTGAATGGGGTAGGATGACCTGCTAATTGGGGGGGGGGATGATGTAG 
matches: 
      ATGTTGCTTATTGTTTTGAATGGGGTAGGATGACCTGCTAATTGGGGGGGGGGATGA 
           ATGGGGTAG 
              ATGACCTGCTAA 
                    ATGTAG 

Answer 2

Проблема в том, что регулярное выражение потребляет символы, которые он соответствует, а затем они не используются снова.

Вы можете решить эту проблему, используя либо совпадение с нулевой шириной (в этом случае вы получите только индекс соответствия, а не совпадающие символы).

В качестве альтернативы вы можете использовать три подобных регулярных выражений, но каждый из них использует разное смещение:

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

Вы могли бы также рассмотреть возможность использования другого подхода, который не предполагает регулярные выражения, как выше регулярное выражение будет быть медленным.

Answer 3

Проблема с такими вещами в том, что вы можете медленно создавать регулярное выражение, правило по правилу, пока у вас не будет что-то, что работает.

Затем ваши требования меняются, и вам нужно начинать все заново, потому что для простых смертных почти невозможно просто перепроектировать сложное регулярное выражение.

Лично я бы предпочел сделать это «старомодным» способом - используйте строковые манипуляции. Каждый этап может быть легко прокомментирован, и если есть небольшое изменение в требованиях, вы можете просто настроить конкретный этап.

Answer 4

Возможно, вам следует попробовать с другими методами, такими как работа с индексами. Что-то вроде:

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

сделать то же самое для других кодонов и посмотреть, соответствуют ли индексы правилу триплета. Кстати, вы уверены, что ген исключает стартовый кодон? (Некоторые ATG можно найти в гене)