Оценочные методы в протеомике

Автор(ы): Гришин Е.М.

Выпуск: 95

Рубрика: Управление в медико-биологических и экологических системах

Год: 2022

Библиография: Гришин Е.М. Оценочные методы в протеомике // Управление большими системами. Выпуск 95. М.: ИПУ РАН, 2022. С.47-61. DOI: https://doi.org/10.25728/ubs.2022.95.3

Дата опубликования: 31.01.2022

Ключевые слова: протеомика, задача о рюкзаке, метод ветвей и границ, параллельные вычисления

Аннотация: Современные математические методы исследования белка, такие как database search и de novo, имеют свои недостатки. При помощи database search невозможно определить белок, который отсутствует в базах данных. Методы de novo позволяют идентифицировать новые белки, но при этом являются очень ресурсоемкими (требуется использование суперкомпьютера). В рамках данного проекта был разработан комплексный подход приближенного анализа исследуемого белка, проводимый на персональном компьютере. Задача качественного и количественного определения исходной последовательности (белка) состоит из трех подзадач. Первая – устранение шумов и выделение пиков по данным масс-спектрометрии. Был разработан алгоритм, сочетающий метод скользящего среднего и технологию вычислительной фотографии HDR. Вторая подзадача – идентификация пиков. Она была сведена к задаче о рюкзаке и решена при помощи метода ветвей и границ. Последняя подзадача – восстановление исходной последовательности по набору фрагментов (пики и их интенсивности). Данная подзадача была решена при помощи построения двоичных деревьев и поиска пути максимальной длины. Все вычисления проводились на ПК с применением технологии параллельных вычислений CUDA.

Author(s): Grishin E.

Article title: Approximate aproach in proteomics

Issue: 95

Year: 2022

Keywords: proteomics, the knapsack problem, the branch and bound method, parallel computing

Abstract: Modern mathematical methods for protein analysis, such as database search and de novo methods, have their own drawbacks. It is not possible to identify proteins that are not included in databases using database search. The de novo methods allow us to identify new proteins but they are very computationally demanding (requiring the use of a supercomputer). In this project a complex approach of approximate protein analysis conducted on a personal computer was developed. A problem of qualitative and quantitative determination of initial sequence (protein) consists of three subproblems. The first one is noise cancellation and peak identification using mass spectrometry data. An algorithm combining a sliding average method and computational photography HDR technology was developed. The second subproblem is peak identification. It was reduced to a knapsack problem and solved using the branch and bound method. The last subproblem is initial sequence reconstruction using a set of fragments (peaks and their intensities). This subproblem was solved by constructing double trees and searching for a path of maximum length. All calculations were performed on a PC using CUDA parallel computing technology.