denisverkhoturov / geney Goto Github PK

В архиве вы можете найти fastq-файл с ридами и fasta-файл с геномом, собранный из этих ридов проверенным тулом.

Архив: SRR2-reads-and-genome.tar.gz

Задача предполагает следующее:
1. Релизовать Parser трейт, который умеет превращать Seq[T] в Seq[String]. Мы выделяем это в отдельный трейт, чтобы затем легче было тестировать.
2. Реализовать Record класс, который является простым Data Transfer Object. В нем не будет никакой логики, только поля.
3. Реализловать Fasta объект, который является обстракцией над файлом. Он принимает путь к файлу и предлагает интерфейс записи в него рекордов, чтение из него. Этот объект реализует Parser[Fasta.Record]

Контракт для парсера:

Parser[T]
+ show :     T  => Seq[String]
+ shows: Seq[T] => Seq[String]
+ read : Seq[String] => Either[String,     T ]
+ reads: Seq[String] => Either[String, Seq[T]]

Тесты:

• специально Record и Parser покрывать тестами не нужно
• класс Fasta уже требует тестирования, но особенно тестировать там нечего

Спецификация: https://ru.wikipedia.org/wiki/FASTA

В результате собранный геном должен записываться в output в формате fasta. Если сборка прошла успешно и геном удалось собрать иначе программа должна завершаться ненулевым кодом и сообщать в stderr об невозможности произвести сборку.
В качестве строки идентификатора для получившейся последовательности можно использовать строку вида geney-cli v.{VERSION}.

Не забываем про спецификацию fasta: https://zhanglab.ccmb.med.umich.edu/FASTA

Сейчас стоит ограничение в 10 секунд на тест, и когда я писал тест с covid-19, то он не успел выполниться

Необходимо написать тест, который произведет нагенерирует случайное количество ридов из генома c большим количеством повторений и убедится, что если их собрать нашим сборщиком, получиться оригинальный геном.

В качестве такого генома предлагаю взять этот стишок:

I know an old lady who swallowed a fly
I don't know why she swallowed the fly
Perhaps she'll die
I know an old lady who swallowed a spider
That wriggled and jiggled and tickled inside her
She swallowed the spider to catch the fly
But I don't know why she swallowed the fly
Perhaps she'll die
I know an old lady who swallowed a bird
How absurd to swallow a bird
She swallowed the bird to catch the spider
That wriggled and jiggled and tickled inside her
She swallowed the spider to catch the fly
But I don't know why she swallowed the fly
Perhaps she'll die
I know an old lady who swallowed a cat
Imagine that. She swallowed a cat.
She swallowed the cat to catch the bird
She swallowed the bird to catch the spider
That wriggled and jiggled and tickled inside her
She swallowed the spider to catch the fly
But I don't know why she swallowed that fly
Perhaps she'll die
I know an old lady who swallowed a dog
What a hog to swallow a dog!
She swallowed the dog to catch the cat
She swallowed the cat to catch the bird
She swallowed the bird to catch the spider
That wriggled and jiggled and tickled inside her
She swallowed the spider to catch the fly
But I don't know why she swallowed that fly
Perhaps she'll die
I know an old lady who swallowed a goat
Opened her throat and down went the goat!
She swallowed the goat to catch the dog
She swallowed the dog to catch the cat
She swallowed the cat to catch the bird
She swallowed the bird to catch the spider
That wriggled and jiggled and tickled inside her
She swallowed the spider to catch the fly
But I don't know why she swallowed that fly
Perhaps she'll die
I know an old lady who swallowed a cow
I don't know how she swallowed the cow
She swallowed the cow to catch the goat
She swallowed the goat to catch the dog
She swallowed the dog to catch the cat
She swallowed the cat to catch the bird
She swallowed the bird to catch the spider
That wriggled and jiggled and tickled inside her
She swallowed the spider to catch the fly
But I don't know why she swallowed that fly
Perhaps she'll die
I know an old lady who swallowed a horse
She's alive and well of course!

Необходимо написать сквозные функциональные тесты, которые будут проверять корректно ли работает наше приложение целиком. Для этого необходимо создать новый модуль (e2e - end-to-end).

Вероятно, какие-то из этих сценариев будут падать на данном этапе - их мы пометим как pendingUnilFixed. Если вкратце, это механизм, который позволяет писать в Tests First подходе, когда нужный функционал еще не реализован или реализован но работает не корректно - наш случай в общем - больше об этом можно прочитать в официальной документации scalatest в разделе org.scalatest.Assertions#pendingUntilFixed.

Также важный момент здесь - тесты должны создавать все нужные файлы в системе для себя сами в стандартной для системы временной директории, про так как это принято делать можно прочитать здесь в ScalaTest User Guide / Sharing fixtures.

Необходимо покрыть следующие сценарии:

• Должен показывать usage-сообщение, если:
  • никакие аргументы не были переданы
• Должен показывать help-сообщение, если:
  • вызван с аргументом -h
  • вызван с аргументом --help
• Должен показывать сообщение об ошибке, если:
  • аргумент -k:
    • отсутствует
    • не является положительным числом (нужна таблица, проверить так же строковые значения)
  • аргумент -f | --format:
    • отсутствует
    • определен как fasta, если input контент:
      • является
      • не является валидным fasta, сообщает об ошибке
    • определен как fastq, если input контент:
      • не является валидным fastq, сообщает об ошибке
    • определен как derive, если input контент:
      • у файла есть расширение .fasta
      • у файла есть расширение .fastq
      • расширение файла не одно из поддерживаемых:
        • показывает предупреждение в stderr о том, что переключается в режим распознования на основе контента
        • успешно распознает fasta контент
        • успешно распознает fastq контент
        • сообщает об ошибке если контент не является валидным fasta или fastq
  • аргумент -i | --input:
    • отсутствует - читает из stdin
    • определен явно:
      • показывает ошибку, если файл:
        • не существует
        • у текущего пользователя нет прав на чтение этого файла
        • является директорией
      • успешно читает файл если он является корректным
  • аргумент -o | --output:
    • отсутствует - пишет в stdout
    • определен явно:
      • показывает ошибку, если файл:
        • уже существует
        • у текущего пользователя нет прав на запись по этому пути
        • является директорией
      • успешно пишет в файл, если он является корректным

Сделать fork master-репозитория и в новой ветке инициализировать базовый "Hello world" проект. Только вместо тривиального вывода фразы в консоль, попутно решим пару простых задачек для разогрева.

Нужно реализовать две функции: одна считает сумму списка, другая находит максимальное число в списке. Заморачиваться на объек не нужно достаточно реализовать пару независимых функций с следующим контрактом - List[Int] => Int.

Подключить scalatest и написать тесты (предпочтительно использовать WordSpec и Matchers, не используйте assert никогда) покрывающие следующие кейсы:

• sum
  • Сумма пустого списка равна нолю
  • Сумма списка равных элементов равна этому элементу умноженному на длину списка. Например, sum(Arrays.asList(5, 5, 5)) == 5 * 3
  • (коммутативность) Сумма списка равна сумме перевернутого списка. Например, sum(Arrays.asList(1, 2, 3)) == sum(Arrays.asList(3, 2, 1))
  • (ассоциативность) Сумма списка равна сумме сумм подсписков Например, sum(Arrays.asList(1, 2, 3, 4)) == sum(Arrays.asList(1, 2)) + sum(Arrays.asList(3, 4))
• max
  • Максимум в пустом списке не определен и бросает ошибку NoSuchElementException (позже мы разберем способы работы с ошибками принятые в фп, пока же нам не стоит об этом думать, просто кидаем ошибку)
  • Максимум списка из одного элемента равен этому элементу
  • Максимум списка содержится в этом списке
  • Если выбрать max из списка до тех пор, пока список не станет пустым, предыдущий max всегда будет больше или равен следующему.

master-репозиторий: https://github.com/denisverkhoturov/geney
SBT Getting Started: https://www.scala-sbt.org/1.x/docs/Getting-Started.html
scalatest: http://www.scalatest.org/quick_start

Подключить в проект библиотеку подсчета процента покрытия кода тестами на основе "мутантов".

Stryker Mutator QuickStart: https://stryker-mutator.io/stryker4s/quickstart

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

Так, предположим, у нас есть получился такой граф:

digraph G {
  AT -> TG [label="ATG" color="red"]
  TG -> GG [label="TGG" color="red"]
  GG -> GC [label="GGC" color="red"]
  GC -> CG [label="GCG" color="red"]
  CG -> GT [label="CGT" color="red"]
  GT -> TG [label="GTG" color="red"]
  TG -> GC [label="TGC" color="red"]
  GC -> CA [label="GCA" color="red"]
  CA -> AA [label="CAA" color="red"]
  AA -> AT [label="AAT" color="red"]
  AT -> TG [label="ATG" color="red"]
}

Тогда шаг за шагом оптимизируя его мы получим вот такой граф:

digraph G {
  AT -> TG [label="ATG"   color="red"]
  TG -> GC [label="TGGC"  color="red"]
  GC -> TG [label="GCGTG" color="red"]
  TG -> GC [label="TGC"   color="red"]
  GC -> AT [label="GCAAT" color="red"]
  AT -> TG [label="ATG"   color="red"]
}

Единообразие кода в проекте - это важный момент, когда дело доходит до работы в команде.

Нам нужно подключить scalafmt в проект. В качестве конфига возьмем готовый, в случае необходимости позже будем его затачивать под нас.

documentation: https://scalameta.org/scalafmt/docs/installation.html
configuration: https://scalameta.org/scalafmt/docs/configuration.html
example: https://github.com/lightbend/cloudstate-ci/blob/master/.scalafmt.conf

Добавить в имя jar версию.
Сделать jar от cli модуля.

Помимо подключения библиотеки описать парсинг аргументов, которые нам потребуются на первом этапе.

java -jar geney.jar [-h | --help] [-k <number> -i <path> -o <path>]

Options:

• -h, --help - show usage.
• -k - the length of k that will be used to build De Bruijn graph.
• -i, --input - input file with reads to be analyzed.
• -o, --output - output file to write the result to.

Библиотека, которую мы планируем использовать: https://github.com/scopt/scopt

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

Сейчас Travis проверяет наше приложение только на Linux, необходимо добавить другие основные операционные системы в конфигурацию, чтобы убедиться что наш код написан действительно кросс-платформенно. Нас интересуют три основные операционные системы:

• Linux
• MacOS
• Windows

Чтобы сделать, читай раздел Testing Your Project on Multiple Operating Systems официальной документации Travis CI Docs.

Для автоматической проверки корректности кода в пулл-реквестах необходимо настроить интеграцию с Travis CI.

Страница проекта на Travis CI: https://travis-ci.org/DenisVerkhoturov/gene
getting started: https://docs.travis-ci.com/user/tutorial

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

В качестве такого генома предлагаю взять гимн всех студентов:

Gaudeamus igitur
Juvenes dum sumus.
Gaudeamus igitur
Juvenes dum sumus.
Post jucundam juventutem
Post molestam senectutem
Nos habebit humus.
Nos habebit humus.
Vita nostra brevis est
Brevi finietur.
Vita nostra brevis est
Brevi finietur.
Venit mors velociter
Rapit nos atrociter
Nemini parcetur.
Nemini parcetur.
Vivant omnes virgines
Faciles, formosae.
Vivant omnes virgines
Faciles, formosae.
Vivant et mulieres
Tenerae amabiles
Bonae laboriosae.
Bonae laboriosae.
Vivat academia!
Vivant professores!
Vivat academia!
Vivant professores!
Vivat membrum quodlibet
Vivant membra quaelibet
Semper sint in flore.
Semper sint in flore.

На данный момент попытка записать данные в уже существующий файл оканчивается ошибкой. Гораздо более удобным решением было бы разрешить запись в существующие файлы с подтверждением от пользователя.

Контракт простой, на входе у нас LazyList[String], где каждый элемент - это рид. На выходе у нас собранный граф (можно хранить в HashMap). Поиск пути или оптимизацию делать не нужно.

Помимо лекций, которые вы посмотрели ранее, вам так же может помочь эта презентация: https://www.cs.jhu.edu/~langmea/resources/lecture_notes/assembly_dbg.pdf

На данный момент времени поиск пути в графе реализован посредством рекурсии, что может привести к переполнению стека. Нужно заменить реализацию на иттеративную или использующую хвостовую рекурсию.

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

-g | --graph = assembled | optimized

Информация о формате dot: https://www.graphviz.org/doc/info/lang.html

Файл .gitconfig на данный момент не работает. И в целом вспомогательные файлы, засоряющие корень проекта - это не очень хорошо.

Я предлагаю, перенести файлы .gitattributes и .gitconfig в новую папку git. Так же в нее добавить файл .gitmessage, содержащий шаблон коммит мессанджа. Туда же перенести наши хуки. И написать скрипт, который будет инициализировать репозиторий для любого, кто начинает работать с проектом.

Структура, которую я предлагаю:

.
├─ assembler
├─ cli
├─ docs
├─ git
│  ├─ hooks
│  │  ├─ commit-msg.d
│  │  │  └─ check-if-message-accords-with-style-guide.sh
│  │  ├─ post-merge.d
│  │  │  └─ update-hooks.sh
│  │  ├─ install.sh
│  │  └─ template.sh
│  ├─ .gitattributes
│  ├─ .gitconfig
│  ├─ .gitignore
│  ├─ .gitmessage
│  └─ init.sh
├─ project
├─ utils
├─ .scalafmt.conf
├─ .sonarcloud.properties
├─ .travis.yml
├─ CODE-OF-CONDUCT.md
├─ CONTRIBUTING.md
├─ LICENSE.md
├─ README.md
├─ build.sbt
├─ geney-logo.svg
└─ stryker.sh

Контент файла .gitconfig:

[core]
    attributesFile = git/.gitattributes
    autocrlf = false
    eol = lf
    excludesFile = git/.gitignore

[commit]
    template = git/.gitmessage

[pull]
    rebase = true

[merge]
    ff = true

Контент файла git/init.sh:

#!/usr/bin/env bash

script_dir=$(dirname "${0}")
git_dir=$(git rev-parse --git-dir)

function main {
  set_git_config
  install_hooks
}

# Adds the project-specific configurations to the repository-level
# configuration file.
function set_git_config {
  git config --local include.path "../git/.gitconfig"
}

function install_hooks {
  for hook_dir in "${script_dir}"/*.d; do
    hook_name=$(basename "${hook_dir}" ".d")
    cp -r "${hook_dir}" "${git_dir}/hooks/"
    cp "${script_dir}/template.sh" "${git_dir}/hooks/${hook_name}"
    chmod -R a+x "${git_dir}/hooks/${hook_name}.d"
    chmod a+x "${git_dir}/hooks/${hook_name}"
  done
}

main "${@}"

Контент файла git/.gitmessage:

# <tag>: (If applied, this commit will) <subject> (Max 72 char)
# |<----   Preferably using up to 50 chars   --->|<------------------->|
# Tags are:
#       feat - a new feature
#        fix - a bug fix
#       docs - changes to documentation
#      style - formatting, missing semi colons, etc; no code change
#   refactor - refactoring production code
#       test - adding tests, refactoring test; no production code change
#      chore - updating build tasks, package manager configs, etc; no production code change
# Example:
# chore: Apply git conventions on the project

# (Optional) Explain why this change is being made
# |<----   Limit each line to a maximum of 72 characters ------------->|
# Example:
# To make life easier on the project the team decided to declare the way
# all the git related activities are made and incorporate the
# instruction about it into the project.

# (Optional) Resolves: <issue> (list related issues and pull-requests)
# |<----   Limit each line to a maximum of 72 characters ------------->|
# Example:
# Resolves: #42

# ----------------------------------------------------------------------
# Remember to:
#   * Capitalize the subject line
#   * Use the imperative mood in the subject line
#   * Do not end the subject line with a period
#   * Separate subject from body with a blank line
#   * Use the body to explain what and why vs. how
#   * Can use multiple lines with "-" or "*" for bullet points in the
#     body
#   * All the lines starting with "#" will be ignored by git thus
#     you can keep these comments stay
# ----------------------------------------------------------------------

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

Таких строк может быть несколько, циклически сдвинутых.
Например, пусть у нас есть k-mer-ы: AB - BC - CD - DE - EA .
Тогда в качестве выхода подойдет любая из строк ABCDE, BCDEA, CDEAB, DEABC, EABCD.

Для первой итерации сойдет самая простая реализация, не нужно пытаться оптимизировать и ускорять - этим займемся позже

• How to apply de Bruijn graphs to genome assembly

Мы какое-то время посидели на scalafmt, но его правил кажется не достаточно. Давайте перейдем на scalafix и кроме всего прочего встроим его в наш CI, чтобы он предупреждал нас о коде, который отформатирован не лучшим образом и заваливал билд, если находит проблемы.

Настроить сборку приложения в исполняемый артефакт - geney.jar. Задача скорее всего полностью решается изменениями в билд скриптах, и маловероятно потребует изменений кода самого проекта. В jar должен собираться так называемый uber jar - в него должны входить все зависимости.

SonarQube - это инструмент статического анализа кода, отлично подходящий для поиска потенциальных "запахов" и уязвимостей в коде не прибегая к его запуску.

Страница проекта на SonarCloud: https://sonarcloud.io/project/configuration?id=DenisVerkhoturov_geney
Getting started: https://sonarcloud.io/documentation/integrations/github/