title: Ð Ð°Ð·ÑÐ°Ð±Ð¾ÑÐºÐ° Ð¿ÑÐ¾Ð³ÑÐ°Ð¼Ð¼Ñ Ð²ÑÑÐ°Ð²Ð½Ð¸Ð²Ð°Ð½Ð¸Ñ Ð³ÐµÐ½Ð¾Ð¼Ð° Ð´Ð»Ñ Ð²ÑÑÐ¾ÐºÐ¾Ð¿ÑÐ¾Ð¸Ð·Ð²Ð¾Ð´Ð¸ÑÐµÐ»ÑÐ½ÑÑ ÑÐ¸ÑÑÐµÐ¼
title: Ð²ÑÐ¿ÑÑÐºÐ½Ð°Ñ ÐºÐ²Ð°Ð»Ð¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¾Ð½Ð½Ð°Ñ ÑÐ°Ð±Ð¾ÑÐ° Ð¼Ð°Ð³Ð¸ÑÑÑÐ°
titleType: Subtitle
title: Genome alignment program implementation for high perfomance systems
Creators: name: ÐÐ°ÑÐ¸Ð»Ð¾Ð², ÐÐ°ÑÐ¸Ð»Ð¸Ð¹
Publisher: name: Ð¡Ð°Ð½ÐºÑ-ÐÐµÑÐµÑÐ±ÑÑÐ³ÑÐºÐ¸Ð¹ Ð¿Ð¾Ð»Ð¸ÑÐµÑÐ½Ð¸ÑÐµÑÐºÐ¸Ð¹ ÑÐ½Ð¸Ð²ÐµÑÑÐ¸ÑÐµÑ ÐÐµÑÑÐ° ÐÐµÐ»Ð¸ÐºÐ¾Ð³Ð¾
Year: 2020
Subjects: ÑÐ¾ÑÑÐ¸ÑÐ¾Ð²ÐºÐ°
Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼
ÑÑÐ¿ÐµÑÐºÐ¾Ð¼Ð¿ÑÑÑÐµÑ
Ð²ÑÑÐ¾ÐºÐ¾Ð¿ÑÐ¾Ð¸Ð·Ð²Ð¾Ð´Ð¸ÑÐµÐ»ÑÐ½ÑÐµ Ð²ÑÑÐ¸ÑÐ»ÐµÐ½Ð¸Ñ
Ð¿Ð°ÑÐ°Ð»Ð»ÐµÐ»Ð¸Ð·Ð¼
Ð±Ð¸Ð¾Ð¸Ð½ÑÐ¾ÑÐ¼Ð°ÑÐ¸ÐºÐ°
Ð²ÑÑÐ°Ð²Ð½Ð¸Ð²Ð°Ð½Ð¸Ðµ Ð³ÐµÐ½Ð¾Ð¼Ð°
ÑÐ¸Ð´Ñ
ÑÐµÐºÐ²ÐµÐ½Ð¸ÑÐ¾Ð²Ð°Ð½Ð¸Ðµ
sorting algorithm
supercomputer
high perfomance computing
concurency
bioinformatics
genome alignment
reads
dna sequencing
ngs

description: Ð¢ÐµÐ¼Ð° Ð²ÑÐ¿ÑÑÐºÐ½Ð¾Ð¹ ÐºÐ²Ð°Ð»Ð¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¾Ð½Ð½Ð¾Ð¹ ÑÐ°Ð±Ð¾ÑÑ: Â«Ð Ð°Ð·ÑÐ°Ð±Ð¾ÑÐºÐ° Ð¿ÑÐ¾Ð³ÑÐ°Ð¼Ð¼Ñ Ð²ÑÑÐ°Ð²Ð½Ð¸Ð²Ð°Ð½Ð¸Ñ Ð³ÐµÐ½Ð¾Ð¼Ð° Ð´Ð»Ñ Ð²ÑÑÐ¾ÐºÐ¾Ð¿ÑÐ¾Ð¸Ð·Ð²Ð¾Ð´Ð¸ÑÐµÐ»ÑÐ½ÑÑ ÑÐ¸ÑÑÐµÐ¼Â». ÐÐ°Ð½Ð½Ð°Ñ ÑÐ°Ð±Ð¾ÑÐ° Ð¿Ð¾ÑÐ²ÑÑÐµÐ½Ð° Ð¿ÑÐ°ÐºÑÐ¸ÑÐµÑÐºÐ¾Ð¼Ñ Ð¿ÑÐ¸Ð¼ÐµÐ½ÐµÐ½Ð¸Ñ Ð¿Ð°ÑÐ°Ð»Ð»ÐµÐ»ÑÐ½ÑÑ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð¾Ð² ÑÐ¾ÑÑÐ¸ÑÐ¾Ð²ÐºÐ¸ Ð¸ Ð¼ÐµÑÐ¾Ð´Ð¾Ð² Ð¿Ð°ÑÐ°Ð»Ð»ÐµÐ»ÑÐ½Ð¾Ð³Ð¾ Ð²Ð²Ð¾Ð´Ð°-Ð²ÑÐ²Ð¾Ð´Ð° Ð´Ð»Ñ Ð·Ð°Ð´Ð°ÑÐ¸ Ð²ÑÑÐ°Ð²Ð½Ð¸Ð²Ð°Ð½Ð¸Ñ Ð³ÐµÐ½Ð¾Ð¼Ð°. Ð ÑÐ°Ð±Ð¾ÑÐµ ÑÐ°ÑÑÐ¼Ð¾ÑÑÐµÐ½Ñ Ð¿Ð¾Ð´ÑÐ¾Ð´Ñ Ðº ÑÐµÐ°Ð»Ð¸Ð·Ð°ÑÐ¸Ð¸ ÑÐ°ÐºÐ¸Ñ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð¾Ð² Ñ ÑÑÑÑÐ¾Ð¼ Ð²Ð¾Ð·Ð¼Ð¾Ð¶Ð½Ð¾ÑÑÐµÐ¹ Ð²ÑÑÐ¾ÐºÐ¾Ð¿ÑÐ¾Ð¸Ð·Ð²Ð¾Ð´Ð¸ÑÐµÐ»ÑÐ½ÑÑ ÑÐ¸ÑÑÐµÐ¼.
Ð¦ÐµÐ»Ñ ÑÐ°Ð±Ð¾ÑÑ â ÑÐ°Ð·ÑÐ°Ð±Ð¾ÑÐºÐ° Ð¿ÑÐ¾Ð³ÑÐ°Ð¼Ð¼Ñ ÑÐ¾ÑÑÐ¸ÑÐ¾Ð²ÐºÐ¸ Ð³ÐµÐ½Ð¾Ð¼Ð°, ÑÑÑÐµÐºÑÐ¸Ð²Ð½Ð¾ÑÑÑ ÑÐ°Ð±Ð¾ÑÑ ÐºÐ¾ÑÐ¾ÑÐ¾Ð¹ Ð·Ð½Ð°ÑÐ¸ÑÐµÐ»ÑÐ½Ð¾ Ð¿ÑÐµÐ²ÑÑÐ°ÐµÑ ÑÑÑÐµÐºÑÐ¸Ð²Ð½Ð¾ÑÑÑ ÑÐ²Ð¾Ð±Ð¾Ð´Ð½ÑÑ Ð¿ÑÐ¾Ð³ÑÐ°Ð¼Ð¼-Ð°Ð½Ð°Ð»Ð¾Ð³Ð¾Ð².
Ð ÑÐ¾Ð´Ðµ ÑÐ°Ð±Ð¾ÑÑ Ð±ÑÐ»Ð¸ ÑÐ°ÑÑÐ¼Ð¾ÑÑÐµÐ½Ñ ÑÐ¿ÐµÑÐ¸Ð°Ð»Ð¸Ð·Ð¸ÑÐ¾Ð²Ð°Ð½Ð½ÑÐµ ÑÐ¾ÑÐ¼Ð°ÑÑ ÑÐ°Ð¹Ð»Ð¾Ð² Ð¿ÑÐµÐ´Ð½Ð°Ð·Ð½Ð°ÑÐµÐ½Ð½ÑÑ Ð´Ð»Ñ ÑÑÐ°Ð½ÐµÐ½Ð¸Ñ Ð±Ð¸Ð¾Ð»Ð¾Ð³Ð¸ÑÐµÑÐºÐ¸Ñ Ð´Ð°Ð½Ð½ÑÑ Ð¸ ÑÑÐ°Ð¿Ñ Ð¾Ð±ÑÐ°Ð±Ð¾ÑÐºÐ¸ ÑÐ°ÐºÐ¸Ñ ÑÐ°Ð¹Ð»Ð¾Ð². ÐÐ»Ñ Ð¾Ð´Ð½Ð¾Ð³Ð¾ Ð¸Ð· ÑÐ¾ÑÐ¼Ð°ÑÐ¾Ð² Ð¿ÑÐµÐ´Ð»Ð¾Ð¶ÐµÐ½Ñ Ð¸ ÑÐµÐ°Ð»Ð¸Ð·Ð¾Ð²Ð°Ð½Ñ ÑÐ»ÐµÐ´ÑÑÑÐ¸Ðµ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ñ:
â¢ ÐÐ»Ð³Ð¾ÑÐ¸ÑÐ¼ Ð¼Ð°ÑÑÐ¸Ð²Ð½Ð¾Ð³Ð¾ Ð¿Ð°ÑÐ°Ð»Ð»ÐµÐ»ÑÐ½Ð¾Ð³Ð¾ Ð²Ð²Ð¾Ð´Ð° Ð¸ Ð²ÑÐ²Ð¾Ð´Ð° Ð´Ð°Ð½Ð½ÑÑ,
â¢ ÐÐ°ÑÐ°Ð»Ð»ÐµÐ»ÑÐ½ÑÐ¹ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼ ÑÐ¾ÑÑÐ¸ÑÐ¾Ð²ÐºÐ¸ Ð½Ð° Ð±Ð°Ð·Ðµ ÑÐ¾ÑÑÐ¸ÑÐ¾Ð²Ð¾ÑÐ½Ð¾Ð¹ ÑÐµÑÐ¸ Ð¿Ð¾Ð´Ð¿Ð¾ÑÐ»ÐµÐ´Ð¾Ð²Ð°ÑÐµÐ»ÑÐ½Ð¾ÑÑÐµÐ¹.
ÐÑÐ¾Ð³ÑÐ°Ð¼Ð¼Ð° ÑÐ¾ÑÑÐ¸ÑÐ¾Ð²ÐºÐ¸ Ð³ÐµÐ½Ð¾Ð¼Ð° ÑÐµÐ°Ð»Ð¸Ð·Ð¾Ð²Ð°Ð½Ð° Ð´Ð»Ñ ÑÑÐ¿ÐµÑÐºÐ¾Ð¼Ð¿ÑÑÑÐµÑÐ° Ñ Ð¸ÑÐ¿Ð¾Ð»ÑÐ·Ð¾Ð²Ð°Ð½Ð¸ÐµÐ¼ ÑÐ·ÑÐºÐ° Ð¡++ Ð¸ ÑÑÐ°Ð½Ð´Ð°ÑÑÐ¾Ð² OpenMP Ð¸ OpenMPI. Ð Ð°Ð·ÑÐ°Ð±Ð¾ÑÐ°Ð½Ð½Ð°Ñ Ð¿ÑÐ¾Ð³ÑÐ°Ð¼Ð¼Ð° Ð´ÐµÐ¼Ð¾Ð½ÑÑÑÐ¸ÑÑÐµÑ Ð·Ð½Ð°ÑÐ¸ÑÐµÐ»ÑÐ½Ð¾Ðµ ÑÐ²ÐµÐ»Ð¸ÑÐµÐ½Ð¸Ðµ ÑÐºÐ¾ÑÐ¾ÑÑÐ¸ ÑÐ°Ð±Ð¾ÑÑ (Ð´Ð¾ 10 ÑÐ°Ð·) Ð¿Ð¾ ÑÑÐ°Ð²Ð½ÐµÐ½Ð¸Ñ ÑÐ¾ ÑÐ²Ð¾Ð±Ð¾Ð´Ð½ÑÐ¼Ð¸ Ð¿ÑÐ¾Ð³ÑÐ°Ð¼Ð¼Ð°Ð¼Ð¸-Ð°Ð½Ð°Ð»Ð¾Ð³Ð°Ð¼Ð¸ Ð±Ð»Ð°Ð³Ð¾Ð´Ð°ÑÑ Ð¼Ð°ÑÑÐ¸Ð²Ð½Ð¾Ð¼Ñ Ð¿Ð°ÑÐ°Ð»Ð»ÐµÐ»ÑÐ½Ð¾Ð¼Ñ Ð²Ð²Ð¾Ð´Ñ-Ð²ÑÐ²Ð¾Ð´Ñ Ð´Ð°Ð½Ð½ÑÑ.
Ð Ð°ÑÑÐ¼Ð°ÑÑÐ¸Ð²Ð°ÐµÐ¼ÑÐµ Ð¿Ð¾Ð´ÑÐ¾Ð´Ñ ÑÐ°ÑÐ¿Ð°ÑÐ°Ð»Ð»ÐµÐ»Ð¸Ð²Ð°Ð½Ð¸Ñ Ð²Ð²Ð¾Ð´Ð°-Ð²ÑÐ²Ð¾Ð´Ð° Ð´Ð°Ð½Ð½ÑÑ Ð¸ Ð¸Ñ Ð¾Ð±ÑÐ°Ð±Ð¾ÑÐºÐ¸ Ð¼Ð¾Ð³ÑÑ Ð¿ÑÐ¸Ð¼ÐµÐ½ÑÑÑÑÑ Ð² Ð´ÑÑÐ³Ð¸Ñ Ð¿ÑÐµÐ´Ð¼ÐµÑÐ½ÑÑ Ð¾Ð±Ð»Ð°ÑÑÑÑ.
description: A main subject of the final qualification work is Â«Development of a genome alignment program for high-performance systemsÂ». This master's thesis covers the practical application of parallel sorting algorithms and parallel input - output methods for the genome alignment problem. A review of existing approaches for implementing such algorithms and methods for high-performance systems is given.
The goal of this work is to develop a genome sorting program that is significantly more efficient than free software analogues.
In the course of the work, specialized file formats intended for storing biological data and the stages of processing such files were considered. The following algorithms are proposed and implemented for one of the formats:
â¢ Massive parallel data input and output algorithm,
â¢ Parallel sorting algorithm based on the subsequence sorting network.
A genome sorting program for a supercomputer using the C++ language with OpenMP and OpenMPI standards was implemented. The developed program demonstrates a significant performance increase compared to free software analogues (up to 10 times) due to massive parallel data input and output.
Described methods of parallelizing data input and output can also be applied in other subject areas.