Как разобрать строку (с помощью «новой» разметки) с помощью R?

Question

Я хочу использовать R для синтаксического разбора строки, который (я думаю) похож на упрощенную разборку HTML.

Например, предположим, что мы имеем следующие две переменные:

Seq <- "GCCTCGATAGCTCAGTTGGGAGAGCGTACGACTGAAGATCGTAAGGtCACCAGTTCGATCCTGGTTCGGGGCA" 
Str <- ">>>>>>>..>>>>........<<<<.>>>>>.......<<<<<.....>>>>>.......<<<<<<<<<<<<." 

Скажи, что я хочу, чтобы разобрать «Seq» По «ул», используя легенду здесь

Seq: GCCTCGATAGCTCAGTTGGGAGAGCGTACGACTGAAGATCGTAAGGtCACCAGTTCGATCCTGGTTCGGGGCA 
Str: >>>>>>>..>>>>........<<<<.>>>>>.......<<<<<.....>>>>>.......<<<<<<<<<<<<. 
    |  | |    | |    |  |    ||  | 
    +-----+ +--------------+ +---------------+  +---------------++-----+ 
     |  Stem 1   Stem 2     Stem 3   | 
     |                | 
     +----------------------------------------------------------------+ 
           Stem 0 

Предположим, что мы всегда имеем 4 стебля (от 0 до 3), но длина букв до и после каждого из них может очень.

Выход должен быть чем-то вроде следующую структуру списка:

list(
    "Stem 0 opening" = "GCCTCGA", 
    "before Stem 1" = "TA", 
    "Stem 1" = list(opening = "GCTC", 
       inside = "AGTTGGGA", 
       closing = "GAGC" 
      ), 
    "between Stem 1 and 2" = "G", 
    "Stem 2" = list(opening = "TACGA", 
       inside = "CTGAAGA", 
       closing = "TCGTA" 
      ), 
    "between Stem 2 and 3" = "AGGtC", 
    "Stem 3" = list(opening = "ACCAG", 
       inside = "TTCGATC", 
       closing = "CTGGT" 
      ), 
    "After Stem 3" = "", 
    "Stem 0 closing" = "TCGGGGC" 
) 

У меня нет никакого опыта программирования синтаксического анализатора, и хотел бы советы относительно того, какую стратегию использовать при программировании что-то вроде этого (и любые рекомендуемые R-команды для использования).

То, о чем я думал, это сначала избавиться от «Stem 0», а затем пройти через внутреннюю строку с рекурсивной функцией (назовем ее «seperate.stem»), которая каждый раз разбивает строку на: 1. Перед стволовой 2. открытие штока 3. внутри ствола 4. закрытие штока 5. после того, как шток

в случае, если «после того, как шток» будет затем рекурсивно вступившего в одной и той же функции («seperate.stem»)

Дело в том, что я не уверен, как попробовать и сделать это кодирование без использования цикла.

Любые советы будут приветствоваться.

Обновление: кто-то прислал мне кучу вопросов, вот они.

Q: Есть ли у каждой последовательности такое же количество «>>>>» для открытия последовательности, как это делает для «< < < <» на окончание последовательности?
A: Да

Q: Есть ли синтаксический анализ всегда начинается с частичным стеблом 0, как ваш пример показывает? A: Нет. Иногда это начинается с нескольких «.».

В: Есть ли способ убедиться, что у вас есть правильные последовательности при запуске? A: Я не уверен, что понимаю, что вы имеете в виду.

В: Есть ли вероятность ошибки в середине строки, с которой необходимо перезапустить? A: К сожалению, да. В этом случае мне нужно будет игнорировать одну из внутренних стеблей ...

Вопрос: Как долго вы должны разбирать эти строки? A: Каждая строка имеет от 60 до 150 символов (и у меня есть десятки тысяч из них ...)

В: Какова каждая отдельная последовательность, как показано в вашем примере, или они продолжаются для тысяч символов? A: каждая последовательность является автономной.

В: Всегда есть хотя бы один '.' между стеблями?
A: Нет

Q: Полный набор правил относительно того, как синтаксический анализ должен быть сделан было бы полезно. A: Согласен. Но, поскольку у меня нет даже базовой идеи о том, как начать кодирование, я сначала подумал, что сначала помог, и попытаюсь настроить другие случаи, которые возникнут, прежде чем обратиться за помощью.

В: У вас есть синтаксис BNF для синтаксического анализа? A: Нет. Ваш e-mail - это первый раз, когда я наткнулся на него (http://en.wikipedia.org/wiki/Backus -Naur_Form).

Answer 1

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

Во-первых, конвертировать Str как вектор отдельных символов, а затем позвонить rle.

split_Str <- strsplit(Str, "")[[1]] 
rle_Str <- rle(split_Str) 

Run Length Encoding 
    lengths: int [1:14] 7 2 4 8 4 1 5 7 5 5 ... 
    values : chr [1:14] ">" "." ">" "." "<" "." ">" "." "<" "." ">" "." "<" "." 

Теперь вам просто нужно разобрать rle_Str$values, который, возможно, проще. Например, внутренний шток всегда будет выглядеть как ">" "." "<".

Я думаю, что главное, что вам нужно подумать, это структура данных. Требуется ли "." между ">" и "<", или это необязательно? У вас есть "." с самого начала? Нужно ли вам обобщать стебли внутри стеблей в стеблях или даже более сложные структуры?

После того, как вы это решите, создание вывода списка должно быть простым.

Кроме того, не беспокойтесь об использовании петель, они находятся на языке, потому что они полезны. Прежде всего, сначала начните работать, а затем подумайте о оптимизации скорости (если вам действительно нужно).