Мне нужен алгоритм, который сообщает, что расстояние редактирования между этими двумя последовательностями равно 2:
GCGGCTCCTCTGGGGCGTTCCC
GCGGCTCCTCTGGGGGGCGTTC
Первое можно преобразовать во второе с помощьювставка из двух символов, например, так:
GCGGCTCCTCTGGGGGGCGTTCCC
GCGGCTCCTCTGGGGGCGTTC
Длина исходных двух строк равнялась 22. Первые 22 символа в этих двух строках теперь идентичны.Расстояние Левенштейна между этими двумя строками равно 4, и я хотел бы сообщить о расстоянии редактирования 2 для этих двух строк.
Есть ли способ сделать это с помощью Python-пакета или функции Levenshtein_distance, которую я уже использую?
Подробнее:
Я применяю это дляДанные следующего поколения.Я хотел бы сравнить 2 последовательности, сгенерированные из части каждого прочитанного секвенирования.Последовательности получены с начала чтения последовательности полной длины и должны быть уникальной последовательностью для чтения последовательности.
Пример:
Чтение A: ATCGAACCGGTT Чтение B: ATGAACCGGTT
Где первые четыре основания строк будут использоваться в качестве уникального идентификатора каждого чтения.Последовательность ATCG является уникальным идентификатором для чтения A, а ATGA - уникальным идентификатором для чтения B. Оба чтения содержат идентичную последовательность «AACCGGTT».При сравнении уникальных идентификаторов (ATCG и ATGA) я хотел бы получить метрику, которая возвращает расстояние редактирования 1 между двумя последовательностями.
Чтение Уникальный идентификатор: ATCG Чтение B уникальный идентификатор после вставки: AT_GA
Причины, по которым я считаю, что выступающие основания на правой стороне строки (конец последовательности) не должны быть оштрафованы, но они должны быть оштрафованы на левой стороне последовательности, следующие:
- Первая и самая важная причина заключается в том, что только потому, что в правой части строки есть выступающие символы (AKA конец последовательности), это не означает, что символы не совпадают между двумясравниваемые последовательности.Это только означает, что у нас нет соответствующих символов из другой последовательности для сравнения.То же самое не верно для левой стороны строки.
- Обычно символы в левой части строки (AKA - начало чтения последовательности) идентифицируются более уверенно (имеют более высокие показатели качества), чем символы в правой части.