Разработки СО РАН - каталоги программ и БД

Назначение - поиск приближенных решений задачи размещения предприятий и фабричного ценообразования (Facility location and pricing problem)

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

Область применения - размещение предприятий, складов, ценообразование.

Используемый алгоритм - двухфазный поиск с чередующимися окрестностями, использующий локальный поиск для определения размещения предприятий и локальный поиск по разным окрестностям для нахождения цен при выбранном размещении. Алгоритм опубликован в статье [1].

Для работы программы необходимо сформировать input.txt файл. 
1) Указать число примеров решаемой задачи (integer).

Для каждого из примеров:
2.а) Указать размерность задачи (число возможных мест открытия предприятий, число клиентов, число открываемых предприятий) и параметры метода решения (максимальное число итераций, максимальное время счета в секундах, максимальное число итераций внутреннего VNS-алгоритма, максимальный размер k окрестности k-flip, глубина просмотра окрестностей k-flip); (все integer)
2.б) Указать матрицу транспортных затрат (строки - возможные места открытия предприятий, столбцы - клиенты); (все double)
2.в) Указать бюджеты клиентов. (все double)
В прилагаемом файле Program1.png. приведен тестовый пример. Результаты работы программы выводятся в файл output.txt. В нем выводятся результаты работы (места, где открыты предприятия, цены, значение целевой функции и время работы) по каждой итерации и лучшее найденное решение в конце. Как видно из результатов расчета (файл Program2.png), на втором примере задачи (файл Program1.png), в найденном решении открыты предприятия в местах 0 и 2, и назначена цена 3 на обоих предприятиях. Итоговый доход равен 12. Время работы менее секунды (округление до целых). 

[1] Кочетов Ю., Панин А., Плясунов А. Сравнение метаэвристик для решения двухуровневой задачи размещения предприятий и ценообразования. Дискретн. анализ и исслед. опер., 2015, том 22, номер 3 с. 36-54. https://doi.org/10.17377/daio.2015.22.480

Функциональные возможности - программа позволяет находить приближенные решения с малой погрешностью для задачи размещения предприятий и фабричного ценообразования. При размерности до 100 возможных мест открытия предприятий и клиентов, при 5 размещаемых предприятиях алгоритм находит решение с погрешностью не более 1%. Ограничение на размерность задачи отсутствует, но при большей размерности требуется больше временных ресурсов.

Инструментальные средства создания - Microsoft visual studio 2012, c/c++.

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

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

Область применения: АСУ, АСУ ТП, лабораторная информационная система (ЛИС), обработка данных ChIP-Seq, RNA-Seq, DNA-Seq.

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

SMITH помогает в сборке проточных ячеек путем подбора образцов с совместимыми баркодами, для того, чтобы не возникало коллизий баркодов на стадии демультиплексирования. С точки зрения пользователя, наиболее важные функции – загрузка образов и отслеживание образов. Загруженные образцы имеют статус «заказан». Перед запуском секвенатора, генерируется виртуальная проточная ячейка, которую подтверждают лидеры групп. После запуска секвенирования по собранной проточной ячейке автоматически генерируется таблица, необходимая для мультиплексирования. По завершению секвенирования, SMITH автоматически отслеживает новые данные, генерируются и исполняются скрипты, которые производят файлы FASTQ, копируют их в нужные директории на сервере, запускают конвейеры обработки, запускают FastQC и отправляют уведомления пользователям, что их данные доступны для анализа. После этого, образец получает статус «проанализирован».

Функциональные возможности: 

• Загрузка образцов
• Аннотирование образцов
• Анализ образцов
• Отслеживание образцов
• Разделение на проекты
• Отслеживание директорий с данными
• Контроль качества
• Политика безопасности
• Хранилище реагентов
• Доступ по ролям
• Виртуальные проточные ячейки
• Совместимость индексов
• Уведомления по email

Програма расчитана на нагрузки в 2-3 эксперимента высокопроизводительного секвенирования. Объем данных одного эксперимента - 40 Гб. Время обработки одного эксперимента 20-36 часов.

Инструментальные средства создания - SMITH была разработана с использованием технологии Java Enterprise и среды разработки NetBeans 7.3. SMITH запускается на сервере приложений Java EE (например, Glassfish). Apache Maven используется как инструмент управления зависимостями.

Архитектура SMITH подразделяется на веб-уровень, срединный уровень и системно-информационный уровень, следуя парадигме Model-View-Controller (MVC). Веб-интерфейс предоставляется средствами Java Server Faces (JSF) и PrimeFaces. Сервлет Faces, который является частью технологии JSF, играет роль контроллера и координирует информационный обмен между пользователем и моделью через набор представлений. Модель основана на технологии JSF Managed Beans – взаимодействующие модули, которые связаны с информационной системой, которая основана на Hibernate с базой MySQL. Отображаемые сообщения выделены в отдельный ресурс для простой интернационализации.

Публикация:

Venco F, Vaskin Y, Ceol A, Muller H.  SMITH: a LIMS for handling next-generation sequencing workflows. BMC Bioinformatics. 2014;15 Suppl 14:S3. doi: 10.1186/1471-2105-15-S14-S3.

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

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

Область применения: биоинформатика, биология, геномика, базы данных, биологические лаборатории.

Используемый алгоритм: Каждый сервис состоит из параметризированного запроса на геномном языке GMQL, короткого описания функций сервиса и формы с параметрами, которые задает пользователь. Детальное описание с биологическими аспектами доступно для нескольких выделенных запросов. Также, для большинства запросов доступны параметры по умолчанию для того, чтобы новые пользователи смогли опробовать сервисы.

Сервисы GQML поддерживают два типа параметров, вводимых пользователем:

• Файловый тип. Файлы, которые загружает пользователь
• Текстовый тип. Любое текстовое значение

Файлы, которые задаются, как входные параметры, загружаются в формате BED и содержат геномные регионы. Сервисы GMQL загружают файлы, конвертируют их во внутренний формат GMQL, выполняют запросы с использованием этих внутренних данных, сохраняют выходные данные и затем удаляют временные данные на сервере. Таким образом, файлы сохраняются на сервере только во время выполнения запроса. Если пользователь задает несколько файлов, то они загружаются на сервер как несколько образцов одного набора данных.

Значения текстовых параметров вставляются напрямую в текст запроса. Например, сервис, который осуществляет выборку образцов из репозитория ENCODE по клеточной линии, используя параметр «cell». Параметр «cell» может принимать различные значения (например, K562, H1-hESC, GM12878, и т.д.), которые соответствуют значениям клеточных линий в репозитории ENCODE. Пользователь выбирает значение параметра и запрос выполняется с этим значением. Для удобства пользователя доступно авто-заполнение значений. Значения подставляются из мета-данных, собранных по всему репозиторию, по мере того, как пользователь печатает в поле параметра.

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

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

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

• Форматом по умолчанию является стандартный выходной формат GMQL – геномные участки в формате GTF (индексация с 0), мета-данные и технические детали выполнения запроса.
• Формат CSV сохраняет все регионы (индексация с 1) с мета-данными всего образца, которые добавляются к каждому региону. Этот формат может быть использован для дальнейшей работы с регионами программным способом.
• Формат BED содержит только геномные регионы (индексация с 1), без мета-данных.

Полученные в результате геномные участки могут быть визуализированы в геномном браузере IGB. Сервисы GMQL используют скриптовый язык IGB и веб-соединение IGB. Геномный браузер IGB должен быть запущен на компьютере пользователя, тогда ссылка, которая доступна в отчете, генерируемом после запуска сервисов, автоматически перенаправит полученные данные в браузер IGB. Данные будут автоматически скачаны с сайта GMQL и загружены в геномный браузер, как треки аннотаций.

Функциональные возможности

• Структурированный доступ к базам данных высокопроизвоидетльного секвенирования
• Автозаполнение параметров
• Загрузка пользовательских файлов
• Асинхронный запуск сервисов
• Генерация результатов в форматах BED, BedGrpah
• Генерация выходных графиков и таблиц (распредеоение участков, тепловая карта участков и т.д.)
• Расширение новыми сервисами с подстветкой синтаксиса для языка GMQL

Сервисы GMQL рассчитаны на обработку коллекций данных объемом до 400Гб. Среднее время выполнения одного из 26-ти встроенных веб-сервисов составляет 5 минут.

Инструментальные средства создания - приложение на фреймворке Django, которое запускается с помощью HTTP-сервера и WSGI сервера Python. Связанные модули Python указаны в файле requirements.txt. Редактируемые переменные окружения безопасности (максимальный размер загружаемого файла, максимальное время выполнения запроса и т.д.) находятся в файле настроек.