Усечение

Разработаны алгоритмы оптимизации функции $\mathrm{imp}(x)$: $$\mathrm{imp}(x)=\frac{\min\{\mathrm{dist}(x,w\mathrm{c}(w))|x=wz\}}{|x|}$$ на некоторых подсловах данной последовательности $x$. Подсловом называют часть слова без пропусков. Основной идеей наших алгоритмов является проверка, является ли одна из оптимальных длин префикса $w$ последовательности $x$ заметно отличающейся от половины длины $x$. Если это так, то программа усекает $x$ на разницу между длинами $w$ и половины $x$. Сложность этих новых алгоритмов линейна в силу линейной сложности операции усечения строки. Кроме того, были разработаны рекурсивные алгоритмы тримминга. Их основной идеей является несколько последовательных усечений $x$ для нахождения длинного подслова $x$ с небольшим значением $\mathrm{imp}(x)$. Ниже приведён пример их программной реализации на языке Python с использованием библиотеки Numba и разработанной в нашей лаборатории программы вычисления функции $\mathrm{imp}(x)$

Функции $pref\_trimmer$, $suff\_trimmer$ и $double\_trimmer$ получают на вход строку $x$, упорядоченный по возрастанию список $optimal\_lengths$ оптимальных длин префикса $w$ и число с плавающей запятой $cutoff\_condition$. Заметим, что $\mathrm{min}(optimal\_lengths)$ и $\mathrm{max}(optimal\_lengths)$ являются первым и последним элементами $optimal\_lengths$ соответсвенно.

Функция $pref\_trimmer$ усекает первые $rd$ символов строки $x$, где $$rd = \mathrm{max}(optimal\_lengths)-\left\lfloor\frac{|x|}{2}\right\rfloor$$ при $$rd \ge |x|\cdot cutoff\_condition.$$

Функция $suff\_trimmer$ усекает последние $ld$ символов строки $x$, где $$ld = \left\lfloor\frac{|x|}{2}\right\rfloor \mathrm{min}(optimal\_lengths)$$ при $$ld \ge |x|\cdot cutoff\_condition.$$

Функция $double\_trimmer$ первоначально вычисляет $$rd = \mathrm{max}(optimal\_lengths)-\left\lfloor\frac{|x|}{2}\right\rfloor$$ и $$ld = \left\lfloor\frac{|x|}{2}\right\rfloor - \mathrm{min}(optimal\_lengths).$$ После этого функция проверяет, выполняются ли неравенства $$rd \ge |x|\cdot cutoff\_condition$$ и $$ld \ge |x|\cdot cutoff\_condition.$$ Если первое неравенство верно, функция усекает первые $rd$ символов строки $x$. Аналогично, если второе неравенство верно, функция усекает последние $ld$ символов строки $x$.

Функции $pref\_GRT$, $suff\_GRT$ и $double\_GRT$ получают на вход строку $x$, числа с плавающей запятой $cutoff\_value$, $imp\_given$ и целое число $recursion\_depth$.

Функция $pref\_GRT$ усекает первые $cutoff\_value\cdot|x|$ символов из $x$, если это возможно, и записывает результат в строку $x'$. Затем вычисляется значение функции $imp(x')$. Если это значение уменьшилось по сравнению с $imp\_given$, то возвращается $pref\_GRT$ от параметров $x'$, $imp(x')$,$cutoff\_value$ и $recursion\_depth-1$. Иначе, возвращается $pref\_GRT$ от параметров $x$, $imp\_given$, $0.5\cdot cutoff\_value$ и $recursion\_depth-1$. Условием выхода из рекурсии является равенство $$recursion\_depth=0.$$ Тогда усечение не будет выполнено и функция вернет входные значения $x$ и $imp\_given$.

Функция $suff\_GRT$ усекает первые и последние $cutoff\_value\cdot|x|$ символов из $x$, если это возможно, и записывает результат в строку $x'$. Затем вычисляется значение функции $imp(x')$. Если это значение уменьшилось по сравнению с $imp\_given$, то возвращается $suff\_GRT$ от параметров $x'$, $imp(x')$,$cutoff\_value$ и $recursion\_depth-1$. Иначе, возвращается $suff\_GRT$ от параметров $x$, $imp\_given$, $0.5\cdot cutoff\_value$ и $recursion\_depth-1$. Условием выхода из рекурсии является равенство $$recursion\_depth=0.$$ Тогда усечение не будет выполнено и функция вернет входные значения $x$ и $imp\_given$.

Функция $double\_GRT$ усекает последние $cutoff\_value\cdot|x|$ символов из $x$, если это возможно, и записывает результат в строку $x'$. Затем вычисляется значение функции $imp(x')$. Если это значение уменьшилось по сравнению с $imp\_given$, то возвращается $double\_GRT$ от параметров $x'$, $imp(x')$,$cutoff\_value$ и $recursion\_depth-1$. Иначе, возвращается $double\_GRT$ от параметров $x$, $imp\_given$, $0.5\cdot cutoff\_value$ и $recursion\_depth-1$. Условием выхода из рекурсии является равенство $$recursion\_depth=0.$$ Тогда усечение не будет выполнено и функция вернет входные значения $x$ и $imp\_given$.

Пример использования

>>> pref_trimmer("AUGCUGACAUAUUUACUAGAGGGUAAAAUUAAUAACCUUCUAGUAAGAGUGGCAGUCG", [28, 30], cutoff_condition = 0.01)
"UGCUGACAUAUUUACUAGAGGGUAAAAUUAAUAACCUUCUAGUAAGAGUGGCAGUC"
>>> suff_trimmer("CUACUUUGCCCCAUUGGGCCUUGUGGUAUAAUUCCAAGGCCCAGCUCGGCAGAGUACAU", [28, 29, 30], cutoff_condition = 0.01)
"CUACUUUGCCCCAUUGGGCCUUGUGGUAUAAUUCCAAGGCCCAGCUCGGCAGAGUACAU"
>>> double_trimmer("UGCCAGGCCCGGGAGUGCAGGGAAGCUCAGGGCCUCCUCUCUUGUCUCCUGGCAGG", [25, 26, 27, 28, 29], cutoff_condition = 0.01)
"GCCAGGCCCGGGAGUGCAGGGAAGCUCAGGGCCUCCUCUCUUGUCUCCUGGC"
>>> pref_GRT("AAAAAAAAAACUACUUUGCCCCAUUGGGCCUUGUGGUAUAAUUCCAAGGCCCAGCUCGGCAGAGUACAU", cutoff_value=0.05, recursion_depth=3, imp_given=0.27536)
('ACUACUUUGCCCCAUUGGGCCUUGUGGUAUAAUUCCAAGGCCCAGCUCGGCAGAGUACAU', 0.18333333333333332)
>>> suff_GRT("CUACUUUGCCCCAUUGGGCCUUGUGGUAUAAUUCCAAGGCCCAGCUCGGCAGAGUACAUAAAAAAAAAA", cutoff_value=0.05, recursion_depth=3, imp_given=0.28985)
('CUACUUUGCCCCAUUGGGCCUUGUGGUAUAAUUCCAAGGCCCAGCUCGGCAGAGUACAUA', 0.21666666666666667)
>>> double_GRT("AAAAAAACUACUUUGCCCCAUUGGGCCUUGUGGUAUAAUUCCAAGGCCCAGCUCGGCAGAGUACAUAAAAAAAAAA", cutoff_value=0.05, recursion_depth=3, imp_given=0.276315)
('ACUACUUUGCCCCAUUGGGCCUUGUGGUAUAAUUCCAAGGCCCAGCUCGGCAGAGUACAUAAAA', 0.234375)

Реализация: `trimmers.py`

Показать код

from palial import imp
import numpy as np
from numba import njit


@njit
def endTrimmer(
    seq: str, optimal_lengths: np.array, cutoff_condition: float = 0.01
) -> str:
    """computes possible right-side-trimming of "seq"
    for a given string "seq" and array "optimal_lengths" of optimal w lengths where w is
    some prefix of seq such that ww' is Levenshtein-closest palindrome to seq(w' is the reverse complement of w).
    Trimming is performed if minimal length of w is smaller than half of the length of seq for more than "cutoff_condition" percents of len(seq)
    >>> endTrimmer("CUACUUUGCCCCAUUGGGCCUUGUGGUAUAAUUCCAAGGCCCAGCUCGGCAGAGUACAU", [28, 29, 30], cutoff_condition = 0.01)
    "CUACUUUGCCCCAUUGGGCCUUGUGGUAUAAUUCCAAGGCCCAGCUCGGCAGAGUACAU"
    """
    left_dist = int(np.floor(len(seq) / 2) - optimal_lengths[0])
    if (left_dist) > cutoff_condition * len(seq):
        return seq[: len(seq) - left_dist]
    return seq


@njit
def begTrimmer(
    seq: str, optimal_lengths: np.array, cutoff_condition: float = 0.01
) -> str:
    """computes possible left-side-trimming  of "seq"
    for a given string "seq" and array "optimal_lengths" of optimal w lengths where w is
    some prefix of seq such that ww' is Levenshtein-closest palindrome to seq(w' is the reverse complement of w).
    Trimming is performed if maximal length of w is smaller than half of the length of seq for more than "cutoff_condition" percents of len(seq)
    >>> begTrimmer("AUGCUGACAUAUUUACUAGAGGGUAAAAUUAAUAACCUUCUAGUAAGAGUGGCAGUCG", [28, 30], cutoff_condition = 0.01)
    "UGCUGACAUAUUUACUAGAGGGUAAAAUUAAUAACCUUCUAGUAAGAGUGGCAGUC"
    """
    right_dist = int(optimal_lengths[-1] - np.floor(len(seq) / 2))
    if (right_dist) > cutoff_condition * len(seq):
        return seq[right_dist:]
    return seq


@njit
def doubleTrimmer(
    seq: str, optimal_lengths: np.array, cutoff_condition: float = 0.01
) -> str:
    """computes possible both-sides-trimming of "seq"
    for a given string "seq" and array "optimal_lengths" of optimal w lengths where w is
    some prefix of seq such that ww' is Levenshtein-closest palindrome to seq(w' is the reverse complement of w).
    left-side-trimming is performed if maximal length of w is smaller than half of the length of seq for more than "cutoff_condition" percents of len(seq)
    right-side-trimming is performed if minimal length of w is smaller than half of the length of seq for more than "cutoff_condition" percents of len(seq)
    >>> doubleTrimmer("UGCCAGGCCCGGGAGUGCAGGGAAGCUCAGGGCCUCCUCUCUUGUCUCCUGGCAGG", [25, 26, 27, 28, 29], cutoff_condition = 0.01)
    "GCCAGGCCCGGGAGUGCAGGGAAGCUCAGGGCCUCCUCUCUUGUCUCCUGGC"
    """
    left_dist = int(np.floor(len(seq) / 2) - optimal_lengths[0])
    right_dist = int(optimal_lengths[-1] - np.floor(len(seq) / 2))
    new_seq = seq
    if (left_dist) > cutoff_condition * len(seq):
        new_seq = seq[: len(seq) - left_dist]
    if (right_dist) > cutoff_condition * len(seq):
        new_seq = new_seq[right_dist:]
    return new_seq


def pref_GRT(
    seq: str, cutoff_value: float = 0.05, recursion_depth: int = 3, imp_given=0.5
) -> Tuple[str, float]:
    """computes possible right-side-trimming of "seq" using recursion.
    If "recursion_depth"==0, then function returns it's input parameters "seq" and "imp_given"
    From a given "seq" it trims first "cutoff_value"*len("seq") symbols and computes
    imp() function for it. If imp value is lower than "imp_given", then pref_GRT returns itself
    with trimmed sequence, newely computed imp and decremented "recursion_depth" value as the parameters.
    If imp value is higher than "imp_given", then function returns itself with same "seq" and "imp_given"
    parameters but decremented "recursion_depth" and halfed "cutoff_value" ones.

    >>> pref_GRT("AAAAAAAAAACUACUUUGCCCCAUUGGGCCUUGUGGUAUAAUUCCAAGGCCCAGCUCGGCAGAGUACAU", cutoff_value=0.05, recursion_depth=3, imp_given=0.27536)
    ('ACUACUUUGCCCCAUUGGGCCUUGUGGUAUAAUUCCAAGGCCCAGCUCGGCAGAGUACAU', 0.18333333333333332)
    """
    if recursion_depth == 0:
        return seq, imp_given
    if len(seq) > int(
        np.floor(len(seq) * cutoff_value)
    ):  
        new_seq = seq[int(np.floor(len(seq) * cutoff_value)) :]
        new_imp = imp(new_seq)
    else:
        new_imp = imp_given

    if new_imp < imp_given:
        return pref_GRT(
            new_seq, cutoff_value, recursion_depth - 1, new_imp
        )
    else:
        return pref_GRT(
            seq, cutoff_value / 2, recursion_depth - 1, imp_given
        )


def suff_GRT(
    seq: str, cutoff_value: float = 0.05, recursion_depth: int = 3, imp_given=0.5
) -> Tuple[str, float]:
    """computes possible left-side-trimming of "seq" using recursion.
    If "recursion_depth"==0, then function returns it's input parameters "seq" and "imp_given"
    From a given "seq" it trims last "cutoff_value"*len("seq") symbols and computes
    imp() function for it. If imp value is lower than "imp_given", then suff_GRT returns itself
    with trimmed sequence, newely computed imp and decremented "recursion_depth" value as the parameters.
    If imp value is higher than "imp_given", then function returns itself with same "seq" and "imp_given"
    parameters but decremented "recursion_depth" and halfed "cutoff_value" ones.

    >>> suff_GRT("CUACUUUGCCCCAUUGGGCCUUGUGGUAUAAUUCCAAGGCCCAGCUCGGCAGAGUACAUAAAAAAAAAA", cutoff_value=0.05, recursion_depth=3, imp_given=0.28985)
    ('CUACUUUGCCCCAUUGGGCCUUGUGGUAUAAUUCCAAGGCCCAGCUCGGCAGAGUACAUA', 0.21666666666666667)
    """
    if recursion_depth == 0:
        return seq, imp_given
    if len(seq) > int(
        np.floor(len(seq) * cutoff_value)
    ):
        new_seq = seq[: len(seq) - int(np.floor(len(seq) * cutoff_value))]
        new_imp = imp(new_seq)
    else:
        new_imp = imp_given

    if new_imp < imp_given:
        return suff_GRT(
            new_seq, cutoff_value, recursion_depth - 1, new_imp
        )
    else:
        return suff_GRT(
            seq, cutoff_value / 2, recursion_depth - 1, imp_given
        )


def double_GRT(
    seq: str, cutoff_value: float = 0.05, recursion_depth: int = 3, imp_given=0.5
) -> Tuple[str, float]:
    """computes possible double-side-trimming of "seq" using recursion.
    If "recursion_depth"==0, then function returns it's input parameters "seq" and "imp_given"
    From a given "seq" it trims first and last "cutoff_value"*len("seq") symbols and computes
    imp() function for it. If imp value is lower than "imp_given", then double_GRT returns itself
    with trimmed sequence, newely computed imp and decremented "recursion_depth" value as the parameters.
    If imp value is higher than "imp_given", then function returns itself with same "seq" and "imp_given"
    parameters but decremented "recursion_depth" and halfed "cutoff_value" ones.

    >>> double_GRT("AAAAAAACUACUUUGCCCCAUUGGGCCUUGUGGUAUAAUUCCAAGGCCCAGCUCGGCAGAGUACAUAAAAAAAAAA", cutoff_value=0.05, recursion_depth=3, imp_given=0.276315)
    ('ACUACUUUGCCCCAUUGGGCCUUGUGGUAUAAUUCCAAGGCCCAGCUCGGCAGAGUACAUAAAA', 0.234375)
    """
    if recursion_depth == 0:
        return seq, imp_given
    if len(seq) > 2 * int(
        np.floor(len(seq) * cutoff_value)
    ):
        new_seq = seq[
            int(np.floor(len(seq) * cutoff_value)) : len(seq)
            - int(np.floor(len(seq) * cutoff_value))
        ]
        new_imp = imp(new_seq)
    else:
        new_imp = imp_given

    if new_imp < imp_given:
        return double_GRT(
            new_seq, cutoff_value, recursion_depth - 1, new_imp
        )
    else:
        return double_GRT(
            seq, cutoff_value / 2, recursion_depth - 1, imp_given
        )

Публикации

G.A. Khaziev, A.V. Seliverstov, O.A. Zverkov. Searching for an imperfect palindrome. Computer algebra: 6th International Conference Materials, Moscow, Russia, June 23–25 2025, Ed. A. A. Ryabenko, D. S. Kulyabov, Moscow: RUDN University, 2025, P. 62–65. DOI: 10.22363/12585-2025-6-000

Усечение

Пример использования

Реализация: trimmers.py

Публикации

Реализация: `trimmers.py`