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

Question

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

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

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

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

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-команды для использования).

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

Где "после ствола" будет затем рекурсивно введен в ту же функцию ("seperate.stem")

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

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

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

В: У каждой последовательности одинаковое число «>>>>» для открывающей последовательности, как у «<<<<» в конечной последовательности? </strong>
A: Да

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

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

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

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

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

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

В: Был бы полезен полный набор правил о том, как должен выполняться синтаксический анализ. 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, что, возможно, проще. Например, внутренний стебель всегда будет выглядеть как ">" "." "<".

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

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

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