Найти подстроки, содержащие определенное количество определенных символов

Раздвижное окно:

• Лучший способ решить эту проблему — написать алгоритм O(N).
• Если количество символов является управляемым, то его можно достаточно хорошо настроить. Если нет, вам нужно написать несколько методов и сделать ваши алгоритмы модульными, чтобы их было легко отлаживать и поддерживать.

Код

def _sliding_window(s, char_a, char_b, count_a, count_b):
    res = []
    starts = []

    for i in range(len(s)):
        char = s[i]

        if char in (char_a, char_b):
            starts.append(i)

    for start in starts:
        As, Bs = 0, 0
        temp = ""

        for i in range(start, len(s)):
            char = s[i]

            if char == char_a:
                As += 1
            if char == char_b:
                Bs += 1

            temp += char

            if As == count_a and Bs == count_b:
                res.append(temp)
                break

    return res


s = "GGACATCGCGGTGGATCGCCACGCGACATCGCGGTGGATCGACGGACATCCGCGGTGCGATCCGACGACATGCGCGCG"

print(_sliding_window(s, 'G', 'C', 2, 1), "\n")
print(_sliding_window(s, 'G', 'C', 3, 0), "\n")
print(_sliding_window(s, 'G', 'C', 1, 2), "\n")
print(_sliding_window(s, 'G', 'C', 0, 3), "\n")

Примечание:

• В приведенном выше алгоритме мы сначала находим начальные индексы, затем выполняем скользящее окно.

• У Силла есть некоторые проблемы с логикой, и я оставлю это вам.

• Если у вас мало данных, вы можете просто использовать алгоритм O(N^ 2), который легко написать.

Принты

['GGAC', 'GCG', 'CGG', 'GGATC', 'GATCG', 'GCG', 'GCG', 'CGG', 'GGATC', 'GATCG', 'GACG', 'CGG', 'GGAC', 'GCG', 'CGG', 'GTGC', 'GCG', 'GACG', 'GACATG', 'GCG', 'GCG', 'GCG'] 

['GGTG', 'GTGG', 'GGTG', 'GTGG', 'GGTG'] 

['GACATC', 'CATCG', 'CGC', 'CGC', 'GCC', 'CACG', 'CGC', 'CGAC', 'GACATC', 'CATCG', 'CGC', 'CGAC', 'GACATC', 'CCG', 'CGC', 'CGATC', 'GATCC', 'CCG', 'CGAC', 'CGAC', 'CATGC', 'CGC', 'CGC'] 

['CCAC', 'CATCC'] 

Шаблон регулярного выражения

Было бы сложно написать шаблон для каждого случая. Но способ написания шаблона следующий.

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

Для 3G в любом порядке:

(?=.*G.*G.*G)([G].*?[G].*?[G])

Код

import re

p = r'(?=.*G.*G.*G)([G].*?[G].*?[G])'

s = """
GGACATCGCGGTGGATCGACGGACATCGCGGTGGATCGACGGACATCGCGGTGGATCGAC GACATGCGCGCG. GGACATGCGCGCGGGACATGCGCGCG. GGACATGCGCGCG. 
GCGG or GTGG, or GGACATCG. GCGG or GTGG, or GGACATGCGCGCG. GGACATGCGCGCG. GGACATGCGCGCGGGACATGCGCGCG. GGACATGCGCGCG. 
GCGG or GTGG, or GGACATCG. GCGG or GTGG, or GGACATGCGCGCG. GGACATGCGCGCG. GGACATGCGCGCGGGACATGCGCGCG. GGACATGCGCGCG. 
"""

find_3G = re.findall(p, s)

print(find_3G)

# Note that 'GCG. G' is also part of those found.

Принты

['GGACATCG', 'GGTG', 'GATCGACG', 'GACATCGCG', 'GTGG', 'GACGG', 'GCGG', «ГГАТКГ», «ГАКАТГКГ», «ГКГ. G', 'GACATGCG', 'GCGG', 'GACATGCG', 'GCG. G', 'GACATGCG', 'GCGG', 'GTGG', 'GGACATCG', 'GCGG', 'GTGG', 'GGACATG', «GCGCG», «GGACATG», «GCGCG», «GGACATG», «GCGCG», «GGACATG», «GCGCG», «GGACATG», «GCGCG», «GCGG», «GTGG», «GGACATCG», «GCGG», «GTGG», «GGACATG», «GCGCG», «GGACATG», «GCGCG», «GGACATG», «GCGCG», «GGACATG», 'GCGCG', 'GGACATG', 'GCGCG']

Наивный алгоритм перебора для двух G и одного C будет следующим O(N ^ 2):

def _pattern(s):
    return s.count('G') == 2 and s.count('C') == 1

def _collect(s):
    res = []
    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            part = s[i:j]
            if _pattern(part):
                res.append(part)
    return res


s = """
GGACATCGCGGTGGATCGACGGACATCGCGGTGGATCGACGGACATCGCGGTGGATCGAC GACATGCGCGCG. GGACATGCGCGCGGGACATGCGCGCG. GGACATGCGCGCG. 
GCGG or GTGG, or GGACATCG. GCGG or GTGG, or GGACATGCGCGCG. GGACATGCGCGCG. GGACATGCGCGCGGGACATGCGCGCG. GGACATGCGCGCG. 
GCGG or GTGG, or GGACATCG. GCGG or GTGG, or GGACATGCGCGCG. GGACATGCGCGCG. GGACATGCGCGCGGGACATGCGCGCG. GGACATGCGCGCG. 
"""
G, C = 2, 1

print(_collect(s))

Принты

['\nGGAC', '\nGGACA', '\nGGACAT', 'GGAC', 'GGACA', 'GGACAT', 'GCG', «CGG», «CGGT», «TGGATC», «GGATC», «GATCG», «GATCGA», «GACG», «ACGG», «ACGGA», «CGG», «CGGA», «GGAC», «GGACA», «GGACAT», «GCG», «CGG», «CGGT», «TGGATC», «GGATC», «GATCG», «GATCGA», «GACG», «ACGG», «ACGGA», «CGG», «CGGA», «GGAC», «GGACA», «GGACAT», «GCG», «CGG», «CGGT», «TGGATC», «GGATC», «GATCG», «GATCGA», «GAC G», «GAC GA», «GACATG», «GACATG», «ATGCG», «TGCG», «GCG», «GCG», «GCG», «GCG.», «GCG.». ', 'КГ. Г', '. ГГАК','. ГГАКА', '. GGACAT», «GGAC», «GGACA», «GGACAT», «GGAC», «GGACA», «GGACAT», «GACATG», «ATGCG», «TGCG», «GCG», «GCG», «GCG», «CGG», «GGAC», «GGACA», «GGACAT», «GACATG», «ATGCG», «TGCG», 'GCG', 'GCG', 'GCG', 'GCG.', 'GCG. ', 'КГ. Г', '. ГГАК', '. ГГАКА', '. GGACAT», «GGAC», «GGACA», «GGACAT», «GGAC», «GGACA», «GGACAT», «GACATG», «ATGCG», «TGCG», «GCG», «GCG», «GCG», «GCG.», «GCG. ', 'ГКГ. \n', 'КГ. \nG', 'Г. \nGC', '. \nGCG', ' \nGCG', '\nGCG', 'GCG', 'CGG', 'CGG', 'CGG o', 'CGG или', 'CGG или', 'или GGAC', 'или GGACA', ' или GGACAT', 'или GGAC', 'или GGACA', 'или GGACAT', 'или GGAC', 'или GGACA', 'или GGACAT', 'r GGAC', 'r GGACA', 'r GGACAT', ' GGAC', ' GGACA', ' GGACAT», «GGAC», «GGACA», «GGACAT», «ATCG. Г», «ТКГ. Г», «КГ. ГАРАНТИРОВАННАЯ ПОБЕДА. ГК', '. GCG', 'GCG', 'GCG', 'CGG', 'CGG', 'CGG o', 'CGG или', 'CGG или ', 'или GGAC', 'или GGACA', 'или GGACAT', 'или GGAC', 'или GGACA', 'или GGACAT', 'или GGAC', 'или GGACA', 'или GGACAT', 'r GGAC', 'r GGACA', 'r GGACAT', 'GGAC', 'GGACA', 'GGACAT', 'GGAC', 'GGACA', 'GGACAT', «GACATG», «ATGCG», «TGCG», «GCG», «GCG», «GCG», «GCG.», «GCG. ', 'КГ. Г', '. ГГАК','. ГГАКА', '. GGACAT», «GGAC», «GGACA», «GGACAT», «GGAC», «GGACA», «GGACAT», «GACATG», «ATGCG», «TGCG», «GCG», «GCG», «GCG», «GCG.», «GCG. ', 'КГ. Г', '. ГГАК','. ГГАКА', '. ГГАКАТ', ' GGAC», «GGACA», «GGACAT», «GGAC», «GGACA», «GGACAT», «GACATG», «ATGCG», «TGCG», «GCG», «GCG», «GCG», «CGG», «GGAC», «GGACA», «GGACAT», «GACATG», «ATGCG», «TGCG», «GCG», «GCG», «GCG», «GCG.», 'ГКГ. ', 'КГ. Г', '. ГГАК','. ГГАКА', '. GGACAT», «GGAC», «GGACA», 'GGACAT', 'GGAC', 'GGACA', 'GGACAT', 'GACATG', 'ATGCG', 'TGCG', 'GCG', 'GCG', 'GCG', 'GCG.', 'GCG. ', 'ГКГ. \n', 'КГ. \nG', 'Г. \nGC', '. \nGCG', ' \nGCG', '\nGCG', 'GCG', 'CGG', 'CGG ', 'CGG o', 'CGG or', 'CGG или', 'или GGAC', 'или GGACA', 'или GGACAT', 'или GGAC', ' или GGACA', 'или GGACAT', 'или GGAC', 'или GGACA', 'или GGACAT', 'r GGAC', 'r GGACA', 'r GGACAT', 'GGAC', 'GGACA', 'GGACAT', 'GGAC', 'GGACA', «GGACAT», «ATCG. Г», «ТКГ. Г», «КГ. ГАРАНТИРОВАННАЯ ПОБЕДА. ГК', '. ГКГ», «ГКГ», «GCG», «CGG», «CGG», «CGG o», «CGG или», «CGG или», «или GGAC», «или GGACA', 'или GGACAT', ' или GGAC', ' или GGACA', ' или GGACAT', 'или GGAC', 'или GGACA', 'или GGACAT', 'r GGAC', 'r GGACA', 'r GGACAT', ' GGAC», «GGACA», «GGACAT», «GGAC», «GGACA», «GGACAT», «GACATG», 'ATGCG', 'TGCG', 'GCG', 'GCG', 'GCG', 'GCG.', 'GCG.', 'GCG. ', 'КГ. Г', '. ГГАК','. ГГАКА', '. GGACAT», «GGAC», «GGACA», «GGACAT», «GGAC», «GGACA», «GGACAT», «GACATG», «ATGCG», «TGCG», «GCG», «GCG», «GCG», «ГКГ.», «ГКГ. ', 'КГ. Г', '. ГГАК','. ГГАКА', '. GGACAT', 'GGAC', ' GGACA», «GGACAT», «GGAC», «GGACA», «GGACAT», «GACATG», «ATGCG», «TGCG», «GCG», «GCG», «GCG», «CGG», «GGAC», «GGACA», «GGACAT», «GACATG», «ATGCG», «TGCG», «GCG», «GCG», «GCG», «GCG.», «GCG.». ', 'КГ. Г', '. ГГАК','. ГГАКА', '. GGACAT», «GGAC», «GGACA», «GGACAT», «GGAC», «GGACA», «GGACAT», «GACATG», «ATGCG», «TGCG», «GCG», «GCG», «GCG», «GCG.», «GCG. ', 'ГКГ. \н']

Примечание

• Этот алгоритм можно записать с временной сложностью O(N). Я просто хотел показать здесь, как мы подходим к решению проблемы.

• Вы можете добавить методы для обработки крайних случаев.

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

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

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

(?=((?:G[^G]*){2}G))

Демо: https://regex101.com/r/ajXtbq/1

Сопоставление подстрок, содержащих две буквы определенных точных чисел, немного сложнее. Все сводится к захвату желаемого количества каждой буквы и захвату того, что следует за ним, а затем захвату подстроки, состоящей из одного из предыдущих захватов нужных букв, за которыми следуют символы, не являющиеся этой буквой, до тех пор, пока она не достигнет точка, где то, что следует, является одним из предыдущих захватов того, что следует за другой желаемой буквой. Ниже приведен пример захвата подстрок ровно с двумя G и одним C:

(?=([^C]*C)(.*$))(?=((?:[^G]*G){2})(.*$))(?=(?=[CG])(\1[^C]*(?=\4$)|\3[^G]*(?=\2$)))

Демо (с желаемыми подстроками, записанными в группе 5): https://regex101.com/r/uCtCfq/1

Для более обобщенного решения для любого количества букв проще и эффективнее использовать счетчик со скользящим окном, который увеличивает конечный индекс, когда счетчик меньше целевого, или увеличивает начальный индекс в противном случае:

from collections import Counter

def find(s, target_counts):
    target_counts = Counter(target_counts)
    current_counts = Counter()
    start = end = 0
    size = len(s)
    while end < size:
        if current_counts < target_counts:
            if (char := s[end]) in target_counts:
                current_counts[char] += 1
            end += 1
        else:
            if (char := s[start]) in current_counts:
                if current_counts == target_counts:
                    yield s[start: end]
                current_counts[char] -= 1
            start += 1

так что:

print(*find("GGACATCGCGGTGGATCGAC", {'G': 2, 'C': 1}), sep='\n')

выходы:

GGAC
GCG
CGG
GGATC
GATCG

Демо здесь

В Python вы можете использовать модуль regex для захвата перекрывающихся совпадений. Это может упростить ваши регулярные выражения. Для 3G вы можете использовать:

G[^G]*G[^G]*G

Для 2 G и 1 C есть три возможные комбинации, как показано ниже (где * представляет собой некоторое количество символов, не являющихся G или C):

1. G*G*C
2. G*C*G
3. C*G*G

Их можно сопоставить с этим регулярным выражением:

G[^GC]*G[^GC]*C|G[^GC]*C[^GC]*G|C[^GC]*G[^GC]*G

В питоне

import regex

s = 'GGACATCGCGGTGGATCGAC'
regex.findall(r'G[^G]*G[^G]*G', s, overlapped=True)

regex.findall(r'G[^GC]*G[^GC]*C|G[^GC]*C[^GC]*G|C[^GC]*G[^GC]*G', s, overlapped=True)

Выход:

['GGACATCG', 'GACATCGCG', 'GCGG', 'GGTG', 'GTGG', 'GGATCG']
['GGAC', 'GCG', 'CGG', 'GGATC', 'GATCG']

Функция Python для поиска всех таких substrings для любого количества букв:

def find_substrings_with_exact_letters(s, letter_counts):
    from collections import Counter

    result = []
    n = len(s)
    total_letters = sum(letter_counts.values())
    
    for i in range(n - total_letters + 1):
        substring = s[i:i + total_letters]
        counts = Counter(substring)
        
        match = all(counts[char] == letter_counts[char] for char in letter_counts)
        
        if match:
            result.append(substring)
    
    return result

# Example usage
s = "GGACATCGCGGTGGATCGCCACGCGACATCGCGGTGGATCGACGGACATCCGCGGTGCGATCCGACGACATGCGCGCG"

letter_counts_3Gs = {'G': 3}
letter_counts_2Gs_1C = {'G': 2, 'C': 1}

substrings_3Gs = find_substrings_with_exact_letters(s, letter_counts_3Gs)
print("Substrings with exactly 3 Gs:", substrings_3Gs)

substrings_2Gs_1C = find_substrings_with_exact_letters(s, letter_counts_2Gs_1C)
print("Substrings with exactly 2 Gs and 1 C:", substrings_2Gs_1C)

измените словарь letter_counts, чтобы найти substrings, соответствующий различным критериям.