BioInf_lab_0

Предисловие

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

Но есть жестокое ограничение по времени - в 10 минут, а также ограничение на оперативную память - моем случае было 30 гб и для самого базового варианта хватает 14, что также можно оптимизировать, например используя алгоритмы хеширования или разряженные таблицы, что требует либо много слишком умственных ресурсов, либо использование сторонних библиотек, что нельзя, а также критически добавляет времени, которое необходимо на обработку

Хжширование по группам также не используется в итоговой версии, так как это, конечно ускоряет итоговый поиск, но даже базовые алгоритмы требуют времени на организацию, что выбивает за 10 минут. Плюс падает точночность.

---

Дерево проекта

.
├── data
│   └── insulin.test.fasta
├── LICENSE
├── main.py
├── README.md
├── requirements.txt
├── results
│   └── index.test.txt
├── test.txt
├── utils.py

---

Установка и запуск проекта

Создание и активация виртуальной среды

macOS / Linux

python3 -m venv venv
source venv/bin/activate

Windows

python -m venv venv
venv\Scripts\activate

Установка зависимостей

pip install --upgrade pip
pip install -r requirements.txt

Запуск проекта

python main.py

Деактивация виртуальной среды

deactivate

---

Пайплан

читаем FASTA -> строим словарь (vocab) всех n-грамм корпуса -> векторизуем каждую последовательность как нормализованный вектор частот n-грамм -> индексируем полученные вектора в оперативной памяти (список разреженных векторов) -> при запросе векторизуем запрос и находим топ-K по косинусному сходству.

Поддерживается гибкость по выбору n (один n или несколько n-значений -> в базовай версии, которая проходит по времени, используется n = (3)).

Решению достаточно простое в силу ограничений.

---

Детальное описание пайплайна

1. Запуск (main)

• fasta_path — путь к базе последовательностей в формате FASTA,
• index_path — путь для сохранения/загрузки индекса,
• n_values — размерность n-грамм (например, 3 или (3,5)). (для того, чтобы влезьть в рамки, рекоммендуется использовать только 3)

---

2. Загрузка индекса (load_index)

Сначала программа пытается загрузить готовый индекс (index.pkl).
Если файл существует, подгружаются:

• vocab — словарь вида n-грамма → индекс,
• reverse_vocab — список индекс → n-грамма,
• vectors — список векторов для всех последовательностей,
• doc_ids — список идентификаторов последовательностей.

---

3. Построение индекса (если файла нет)

3.1. Чтение FASTA (read_fasta)

Файл в формате FASTA разбирается на список кортежей (seq_id, sequence).

3.2. Предобработка корпуса (preprocess_corpus)

Состоит из двух шагов:

• Построение словаря (build_vocab)
  Из всех последовательностей извлекаются n-граммы (для всех n в n_values).
  Формируется vocab {строка: индекс} и reverse_vocab {наоборот}.

• Построение векторов (compute_vector)
  Каждая последовательность преобразуется в нормированный вектор:

  1. вычисляются частоты n-грамм,
  2. частоты переводятся в индексы по vocab,
  3. выполняется L2-нормировка.
     Все векторы сохраняются в список vectors, а идентификаторы — в doc_ids.

3.3. Сохранение индекса (save_index)

Итоговый набор данных (vocab, reverse_vocab, vectors, doc_ids) сохраняется в index.pkl для дальнейшего использования.

---

4. Поисковый запрос (search)

4.1. Векторизация запроса (compute_vector)

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

4.2. Подсчёт сходства (cosine_similarity)

Для каждого документа вычисляется косинусное сходство с запросом.
Так как все векторы нормированы, скалярное произведение соответствует косинусу.

4.3. Выбор лучших (heapq.nlargest)

Из всех кандидатов выбирается top-K наиболее похожих последовательностей.

---

5. Вывод результата

Программа печатает список пар:
(сходство, идентификатор последовательности).