Повторные последовательности в ДНК

Постановка задачи

s = "AAAAAAAAAAAAA"

["AAAAAAAAAA"]

s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

["AAAAACCCCC","CCCCCAAAAA"]

Решение

Задача поиска повторных последовательностей в ДНК имеет средний уровень сложности. Для новичка она неочевидна: прямолинейный перебор всех подстрок с их сравнением друг с другом приведет к квадратичной сложности O(n²), что слишком медленно для длинных цепочек ДНК.

Эта задача - классический пример обработки биоинформатических данных, где на практике подобные алгоритмы используются для поиска генетических аномалий, идентификации повторяющихся участков генома и анализа эволюционных связей. В реальном мире ДНК содержит миллиарды нуклеотидов, поэтому умение находить дубликаты эффективно - это вопрос не только скорости, но и требуемой памяти.

Основная трудность здесь заключается в поиске способа эффективно запоминать уже увиденные фрагменты. Мы уже знаем, что с этим хорошо справляются хеш-таблицы, и тогда задача фактически становится простой, так как сводится к одному проходу по строке.

Хеш-таблица позволяет мгновенно (в среднем за O(1)) проверять, встречался ли текущий фрагмент ранее, превращая сложную проблему поиска дубликатов в простую операцию подсчета.

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

Идея решения:

Идея решения проста. Заведем хеш-таблицу seen для учета подстрок. Ключом будет подстрока длины 10, а в качестве значения - счетчик количества вхождений этой подстроки.

Далее идем циклом по строке s и для каждого окна размером 10, начинающегося с текущего индекса:

• берем подстроку s[i:i+10]
• увеличиваем значение счетчика для этого ключа в хеш-таблице
• если для этой подстроки счетчик стал равен 2, значит, мы встретили повтор
  • добавляем его в результат

Если длина строки n, а размер нашего окна 10, то мы должны двигаться по строке от 0 до n - 10 включительно. То есть условие окончания цикла можно выразить как i <= len(s) - 10.

Оценка сложности

Временная сложность

Временная сложность такого решения линейна O(n), так как мы делаем около n итераций цикла, и в каждой итерации у нас O(1) операций. Ключи имеют константный размер 10, и получение подстроки и операции с хеш-таблицей занимают константное время O(1).

Пространственная сложность

Так как мы храним ключи в хеш-таблице, то пространственную сложность можно считать равной O(n).

Код решения

Итак, код решения будет выглядеть следующим образом:

func findRepeatedDnaSequences(s string) []string {
	seen := map[string]int{}
	result := []string{}
	for i := 0; i <= len(s)-10; i++ {
		part := s[i : i+10]
		seen[part]++
		if seen[part] == 2 {
			result = append(result, part)
		}
	}
	return result
}
 

Скользящий хеш

В этой задаче можно пойти чуть дальше и использовать битовые маски для скользящего хеша (Rolling Hash). Скользящий хеш - это хеш-функция, которая обрабатывает входные данные в рамках перемещающегося скользящего окна.

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

Поскольку у нас всего 4 типа нуклеотидов, мы можем представить каждый из них 2 битами:

• A: 00
• C: 01
• G: 10
• T: 11

Таким образом, последовательность из 10 символов превращается в число из 20 бит, которое легко помещается в обычный int32. Нам не нужно будет каждый раз вырезать подстроку s[i:i+10] на каждой итерации. Мы просто сдвигаем наш текущий хеш на 2 бита и добавляем 2 новых бита.

Вот как это выглядит в коде:

function findRepeatedDnaSequences(s) {
    const seen = new Map();
    const result = [];
    let currentHash = 0;
    for (let i = 0; i < s.length; i++) {
        let bits;
        switch (s[i]) {
            case 'A': bits = 0; break;
            case 'C': bits = 1; break;
            case 'G': bits = 2; break;
            case 'T': bits = 3; break;
        }
        currentHash = ((currentHash << 2) | bits) & 0xfffff;
        if (i >= 9) {
            const count = (seen.get(currentHash) || 0) + 1;
            seen.set(currentHash, count);
            if (count === 2) {
                result.push(s.substring(i - 9, i + 1));
            }
        }
    }
    return result;
}

Если длина подстроки больше 10, то для вычисления ключа мы можем использовать подход из алгоритма Рабина-Карпа.

h = h * b + s[i+k] - s[i] * (b ^ k)

где:
- b - основание системы счисления (например, 31)
- k - длина окна
- s[i] - символ, который уходит из окна
- s[i+k] - символ, который входит в окно

Итоги

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

1. Простота реализации. Это самый читаемый и лаконичный подход на любом языке.

2. Эффективность. По времени O(n) - мы проходим по строке всего один раз. Несмотря на то, что создание подстрок (s[i:i+10]) и их хеширование занимают время, при фиксированной длине окна (10) эти операции можно считать константными O(1) относительно общей длины строки.

3. Количество ключей. O(min(4¹⁰, n)) - для большинства практических задач 10-20 МБ оперативной памяти не являются критичными.

4. Универсальность. Этот метод легко адаптировать под любой алфавит (не только A, C, G, T) и любую длину окна, просто изменив константы.