Information Technology and Systems 2015
An IITP RAS Interdisciplinary Conference & School
September, 7-11, Olympic Village, Sochi, Russia
ISBN: 978-5-901158-28-9

Russian | English

 

 

Subscribe

 

Organizers

IITP RAS

 

Partners

 


Troitskiy variant

STRF

Monday, September 7
14:30 - 16:30
Flagman 3-4
Session: Posters AnnouncementITaS
Chair: Dr.Sci. Mikhail Gelfand

Olga Malyugina, Dmitry Nikolaev
Performance measures for detection and classification in a stream of objects Downoad paper
Abstract: В данной работе исследуется вопрос формальной оценки качества работы распознающей системы, совмещающей этапы детектирования и классификации объектов. Исследование проводится на базе классификатора транспортных средств «АКТС», установленного на платных дорогах для автоматического определения стоимости проезда. Проводится типизация возможных ошибок такого рода систем по отношению к их влиянию на результат работы. Рассматриваются разумные требования к критериям качества и приводятся примеры правдоподобных критериев, которые им не удовлетворяют. В результате предложена группа критериев, удовлетворяющая этим требованиям.

Timofey Chernov, Dmitry Nikolaev, Vitali Kliatskine
Periodic pattern localization on document images Downoad paper
Abstract: Многие документы содержат повторяющиеся защитные элементы, такие как голограммы, водяные знаки, гильоши. Целью нанесения таких периодических фоновых элементов является защита от подделывания. Нахождение подобных структур обеспечивает встроенным системам оптического распознавания символов (OCR) возможность изменять настройки в зонах присутствия защитных элементов, а также повышать точность путем удаления этих элементов с максимально возможным сохранением текстовой информации документа. В этой статье мы предлагаем метод поиска периодических паттернов, основанный на дискретном преобразовании Фурье.

Anastasiya Ingacheva, Marina Chukalina, Dmitry Nikolaev, Aleksey Buzmakov, Victor Prun
A criterion for numerical assessment of restoring artifacts severity for the possibility of further assessing the quality of the reconstruction in the case using of polychromatic mods for sensing X-ray tomography Downoad paper
Abstract: В статье рассматривается влияние применения полихроматического рентгеновского пучка для зондирования в методе рентгеновской томографии на точность реконструкции изображений. Проводится анализ 2-мерного варианта задачи. Для изучения влияния параметров эксперимента на выраженность артефактов численно реализована программа моделирования результатов эксперимента. Предложен критерий численной оценки выраженности артефактов восстановления с точки зрения возможности дальнейшей оценки качества реконструкции. Представлены и обсуждаютсярезультаты применения критерия к модельным расчетам для разных композиций химических элементов.

Revenko Rina
A new post-quantum cryptosystem based on newly discovered decoding algorithm of Reed-Muller codes Downoad paper
Abstract: One of the most important problem of cryptography is the design of cryptosystems (if possible) that are secure against quantum computers. From this point of view the code-based cryptography, which was born in McElice paper in 1978, is the candidate number one. But despite of many efforts and publications we don’t know if schemes of this type are secure even against attacks by ordinary computer. In this talk we propose a new public-key cryptosystem of McElice type which is based on recently invented decoding algorithm for binary Reed-Muller codes. The new scheme looks more secure against structured attacks which led to previously done breaking of McElice type scheme based on generalized Reed-Solomon codes and on Reed-Muller codes.

Semen Korolev, Oleg Zverkov, Sergei Lyzhin, Alexander Seliverstov, Vassily Lyubetsky
A Search for Genes Encoding Histidine-Containing Leader Peptides in Actinobacteria Downoad paper
Abstract: A large-scale search for leader peptides was conducted in Actinobacteria made it possible to predict a mechanism of regulation of translation initiation. This mechanism relies on the interaction between the ribosome translating the leader peptide and the RNA helix potentially overlapping the ribosome-binding site.

Nadezhda Potapova, Maria Andrianova, Georgii Bazykin, Alexey Kondrashov
Accumulation of mutations in nonsense alleles of Drosophila melanogaster Downoad paper
Abstract: Mutations are the sine qua non of evolution; they also shape variation. Even deleterious mutations may segregate within a population for multiple generations if selection against them is not too strong. Point mutations in coding regions of genes may be synonymous if they don't change the encoded amino acid; nonsynonymous if they change it; or nonsense if they result in a premature stop codon. As a nonsense mutation pseudogenizes the gene, it effectively disables negative selection at a gene, making subsequent accumulation of nonsynonymous mutations at other positions of the same gene neutral. Therefore, in the absence of recombination, post-nonsense nonsynonymous mutations are expected to accumulate at the same rate as synonymous mutations. Here, we verify this hypothesis using genomes of 162 inbred lines Drosophila melanogaster. We identified 960 genes with 1202 nonsense mutations. On average, each line carries 63 nonsense mutations in 59 genes. The number of nonsynonymous mutations nested within nonsense alleles may be used to estimate the age distribution of such mutations, and therefore, the period of time for which they segregate in the population.

Alexey Mastov, Ivan Konovalenko, Anton Grigoryev
Adaptive approach to the recognition of objects with arbitrary angle in real time Downoad paper
Abstract: Задача распознавания объектов с произвольного ракурса в реальном времени рассмотрена в рамках проекта по созданию автономного наземного робота. Для ее решения был использован алгоритм random ferns, основанный на парадигме особых точек с адаптивным выбором дескрипторов. В данной статье приводится описание адаптации этого алгоритма к решению задачи поиска объектов в видеопотоке в реальном времени.

Nina Malayr, Elena Maximova, Vera Talis
Analysis of the kinematics of ascent and descent with stairs for children and adolescents diagnosed with early infantile autism Downoad paper
Abstract: Цель настоящей работы - анализ кинематики подъема на ступеньку у подростков с диагнозом Ранний Детский Аутизм (РДА) и анализ кинематики спуска со ступеньки у детей и подростков с РДА в сравнении со здоровыми детьми и подростками. Ранее нами был изучен процесс подъема на ступеньку больных детей. В настоящем исследовании получено, что, также как и у детей с РДА, у больных подростков при подготовке к подъему наблюдались значительно большие колебания амплитуды угловой скорости тазобедренного сустава в сагиттальной плоскости, чем у здоровых ровесников: в 14% проб у подростков с РДА основному минимуму угловой скорости тазобедренного сустава предшествовал, по крайней мере, еще один минимум, с амплитудой ниже порогового. Среди здоровых подростков данное явление было замечено в 5% проб. Однако при анализе процесса спуска данная тенденция сохранялась только в случае сравнения больных и здоровых подростков (дополнительные минимумы в 50% и 15% проб соответственно), а у здоровых детей дополнительные пики наблюдались чаще, чем у больных (16% и 6% соответственно). Также было обнаружено, что при спуске больные подростки меньше разгибали голеностопный сустав, чем их здоровые сверстники, чего не отмечалось во время подъема. Этих различий в изменении голеностопного угла между больными и здоровыми детьми, как при спуске, так и при подъеме не отмечалось. Мы предполагаем, что возрастные особенности кинематики целевого движения ногой при постановке ее на опору при подъеме и спуске дают представление о развитии позного контроля больных РДА, в частности, свидетельствуют об ухудшенной координации больных подростков по сравнению с больными детьми и здоровыми ровесниками.

Igor Kargin
Analysis of the wireless multihop network with random access and low latency Downoad paper
Abstract: В данной работе в рамках концепции Тактильного Интернета рассматриваются многошаговые беспроводные сети. Предлагается модификация метода доступа к среде ALOHA, позволяющая снизить время доставки пакетов в сети. Также в работе роведено сравнение производительности базового метода доступа ALOHA и метода, предложенного авторами.

Dmitriy Vinogradov, Mikhail Gelfand
Analysis of tissue-specific expression in the salivary glands of medicinal leeches Downoad paper
Abstract: Пиявки - подвид кольчатых червей - применялись в медицинской практике как минимум со времен Гиппократа. Несмотря на столь давнюю историю, современная медицина не прекращает их использование. Гирудотерапия применяется в России, Европе и США для лечения таких заболеваний как варикоз и геморрой, а также для устранения венозоного застоя после пересадки органов. Одним из наиболее существенных факторов лечебного воздействия на пациента, является влияние активных веществ, содержащихся в слюне пиявок. В данной работе мы приводим данные по анализу экспрессии генов в слюнных железах и мышечной ткани трех видов медицинских пиявок (Hirudo medicinalis, Hirudo orientalis и Hirudo verbana). Гены, экспрессирующиеся в слюнных железах, но не в мышечной ткани, являются перспективными кандидатами на дальнейшее экспериментальное исследование.

Alexander Ivanov, Zankin Vitaly, Evgeny Khorov
Analytical Model of QoS sensitive data streaming via periodic reservations and Stop-and-Wait ARQ Downoad paper
Abstract: Большинство технологий беспроводной связи (например Wi-Fi) позволяют станциям сети заранее резервировать канал для передачи своих данных. В частности, широко распространен подход периодических резервирований, когда станция резервирует последовательность периодических интервалов времени одинаковой длительности. Резервирование канала обеспечивает защиту от коллизий, а потому целесообразно при передаче данных, предъявляющих требования к качеству обслуживания (QoS-требования). Однако ошибки могут возникать вследствие случайных помех, присущих беспроводной среде. Поэтому необходимо выбирать параметры резервирований с учетом времени, необходимого на дополнительные попытки передачи, которое зависит от используемого протокола повторной передачи (ARQ). В данной работе построена аналитическая модель передачи мультимедийных данных с помощью периодических резервирований и протокола Stop-and-Wait ARQ. Модель позволяет определить период и длительность зарезервированных интервалов, при которых выполнены QoS-требования передаваемых данных.

Elena Kuznetsova, Alena Ivanova
Applied features of training of neural network classifiers in the industrial problems of pattern recognition Downoad paper
Abstract: Описаны распространенные проблемы построения нейросетевых классификаторов на несбалансированных данных, полученных с сенсоров в режиме реального ограниченного времени. Предложен алгоритм синтеза данных с использованием известных методов обработки изображений для увеличения объема и устранения несбалансированности обучающей выборки. Приведены результаты вычислительных экспериментов, демонстрирующие повышение качества работы классификатора при использовании алгоритма синтеза данных на примере задачи классификации образов символов на фотографиях паспортов РФ. Рассмотрен вопрос построения векторов входных признаков классификатора на основе изображений обучающей выборки, предложен метод нормализации яркости изображений при формировании векторов признаков. Приведены вычислительные эксперименты, показывающие целесообразность использования регуляризации для улучшения обобщающей способности классификатора. Исследован вопрос выбора архитектуры классификатора, обеспечивающей наилучшее качество классификации при существующих ограничениях на быстродействие работы алгоритма в реальном времени.

Artem Dyuba, Arthur Zalevsky, Andrey Golovin
Calculated circular dichroism spectra of homo- and heteropolar G-quadruplexes Downoad paper
Abstract: CD spectra of model homo- and heteropolar quadruplex structures are calculated using TDDFT method and classical dipole-dipole interaction model. Quantum chemical calculation yielded CD shapes that closely resemble experimental ones. Classical model allows for fast qualitative theoretical estimate of CD spectrum of an arbitrary quadruplex structure and can be utilized for tracking molecular dynamics trajectories. The dependence of CD spectrum on geometrical parameters is investigated. It is shown that the shape of CD spectrum is determined by stacking regime rather than quadruplex topology.

Vera Talis, Alexandr Notchenko, Oleg Kazennikov
Change in weight distribution for torso rotation in symmetrical and non-symmetrical stance Downoad paper
Abstract: Исследовали регуляцию вертикальной позы при поворотах направо и налево у 12 здоровых испытуемых в симметричной и несимметричной (большая нагрузка на правую или левую ногу) стойке. Получено, что индекс асимметрии в симметричной стойке составлял 1.4%, а в несимметричной -46.6%.(при большей нагрузке правой ноги) и 40.9%( при большей нагрузке левой ноги). При повороте направо из симметричного стояния нагрузка на левую ногу увеличивалась: индекс асимметрии увеличился и составил 9,53%, а при повороте налево индекс асимметрии стояния уменьшился до -3,72%. При стоянии с перегрузкой правой ноги поворот направо привел к тому, что: индекс асимметрии стал -48.4%, а поворот на лево привел к тому, что индекс асимметрии стал -55.0%. При стоянии с перегрузкой левой ноги поворот направо привел к тому, что индекс асимметрии стал 52.1%, а поворот налево изменил индекс асимметрии до 48.0%. Высказывается предположение, что при стоянии с неравномерной нагрузкой на ноги участие ноги в поддержании вертикальной позы зависит от нагрузки, приходящейся на ногу.

Artem Krasilov, Evgeny Khorov, Anton Kiryanov
Channel access in IEEE 802.11ad networks: open issues and possible solutions Downoad paper
Abstract: Одним из перспективных подходов к увеличению скорости передачи данных в беспроводных сетях следующих поколений, является использование диапазонов частот более 60 ГГц. Опубликованный в 2012 г. стандарт IEEE 802.11ad, определяющий принципы работы сетей Wi-Fi в диапазоне частот 60 ГГц, вводит новый метод доступа к беспроводному каналу. При этом стандарт определяет лишь базовые правила, по которым устройства сети могут получать доступ к каналу, но не определяет когда и какой объем канальных ресурсов необходимо выделить каждому устройству. В данной работе проведен анализ открытых задач, возникающих при использовании нового метода доступа для обслуживания различных типов трафика, а также приведен обзор возможных подходов к решению этих задач.

Ekaterina Krymova, Karina Ashurbekova, Vadim Ushakov
Classification of states of a human given MEG data Downoad paper
Abstract: В данной работе проводится анализ данных, полученных методом магнитной энцефалографии, записанных с коры головного мозга, когда человек по сигналу поднимает и опускает палец. Целью настоящей работы является классификация временного сигнала по определенным участкам активности испытуемого. Для этого исходный сигнал сначала был отфильтрован для правильного определения пиков, а также очищен от артефактов. Далее, с помощью библиотек Python MNE и PyEEG были определены эпохи, из которых извлекались признаки. В заметке приводятся результаты сравнения работы различных методов классификации для решения задачи классификации состояний человека на условные состояния внимательности и невнимательности.

Anna Kaznadzey, Pavel Shelyakin
Co-evolution of carbohydrate metabolism genes of same and different functional classes in bacteria Downoad paper
Abstract: The aim of this research was to study bacterial genes related to carbohydrate metabolism, focusing on co-evolution of genes of same and different function classes. After thorough analysis of carbohydrate gene cassettes as well as loner-genes among different bacteria we came to the conclusion that genes of only a little number of functions have a strong tendency to be located within the same cassettes, while most gene classes don't have co-location preferences. We present a classification of all the cases where class pairs do or don't have co-location preferences. Interestingly, genes of the same function class in most cases do have co-location preferences, so their respective cassettes contain several genes with similar functions, like glycosidases or glycosyltransferases. Such cassettes can be regarded as a "tool box" required for a certain similar step in a number of metabolic pathways, which is useful for the organism and is passed on through horizontal transfer.

Ella Tyuryumina, Alexey Neznanov
Combined mathematical model of the growth of breast cancer Downoad paper
Abstract: Работа посвящена математическому моделированию развития опухолевого процесса рака молочной железы (РМЖ). Рассмотрены возможности использования классических математических моделей (экспоненциальная, логистическая, модели Гомперца и фон Берталанфи) для описания роста первичной опухоли и вторичных отдаленных метастазов РМЖ. Предложена новая «объединенная математическая модель роста первичной опухоли и вторичных метастазов РМЖ», основанная на модели экспоненциального роста и состоящая из системы детерминированных нелинейных и линейных уравнений. Объединенная математическая модель роста РМЖ корректно описывает как рост первичной опухоли (вписывается в классификацию РМЖ по критерию Т), так и рост вторичных метастазов, а также хорошо согласуется с данными 10-15-летней выживаемости больных РМЖ в зависимости от стадии РМЖ (критерий М). Анализ «скрытого периода» роста вторичных отдаленных метастазов РМЖ помогает понять причину различий 15-летней выживаемости больных РМЖ в зависимости от стадии РМЖ. Предложенная модель и реализующее её программное средство повышает точность прогноза развития РМЖ и позволяет оптимизировать проведение диагностики вторичных отдаленных метастазов.

Mikhail Moldovan, Svetlana Petrova
Comparative genomics analysis of thiamine-pyrophosphate riboswitches in fungal genomes Downoad paper
Abstract: Riboswitches are conserved sequences on mRNA that can form a secondary structure, able to bind small molecules and change its conformation on binding, thus being able to regulate gene expression. It is known that bacteria use riboswitches extensively. However, only thiamine-pyrophosphate (TPP) riboswitches were found in eukaryotes. In our study we analyzed fungal riboswitches and identified 256 riboswitch-like structures in 186 fungal genomes associated with five orthological gene groups. We studied three of them and found features of regulation proposed for gene hydroxymethilpyrimidine-synthase (nmt1) in most cases. Our data shows that thiazole-synthase (thi4) is regulated in the same fashion. Genes from the third group that corresponds to putative transporter are always regulated via TPP-riboswitches and the principle of this regulation seems to be very conserved. In subphylum Pezizomycotina all enzyme (thi4 and nmt1) genes are regulated via TPP-riboswitches whereas in subphylum Saccaromycotina no riboswitch-like structures as well as putative transporter genes were found.

Olga Sigalova, Dmitry Rodionov
Comparative Genomics of Arginine Biosynthesis Pathways and Regulons in Human Microbiome Downoad paper
Abstract: The aim of the Human Microbiome Project (HMP) is to infer metabolic interconnections between diet and microbiome composition. This study was devoted to the systematic analysis of arginine de novo biosynthesis, transport and regulation in HMP bacteria with significance to human health. We used a subsystems-based comparative genomics approach to reconstruct arginine biosynthesis and salvage patwhays and ArgR transcriptional regulons in diverse bacterial genomes from the HMP project. In the Bacteroidetes phylum we predicted a novel isoform of N-acetylglutamate synthase, which is non-orthologous to known enzymes catalyzing acetylation of L-glutamate on the first step of arginine biosynthesis. As result, for each analyzed HMP microorganism we assigned the arginine prototrophic or auxotrophic phenotype and predicted arginine uptake transporters and ArgR regulon composition in many of them. The results of this study can be useful for understanding metabolic interactions between the members of human microbiota.

Nikita Kotlyarov, Pavel Prikhodko
Comparison of algorithms FAST and CSTA designed to estimate the Sobol indices Downoad paper
Abstract: В работе рассматриваются различные способы оценки главных и общих индексов Соболя. Продемонстрирована зависимость величины ошибки оценки от истинного значения индексов и бюджета вычислений. Детально рассматриваются рассматриваются методы FAST и CSTA, а также их различные вариации, позволяющие произвести более качественную оценку. Указаны рекомендации по выбору того или иного способа оценки в зависимости от ограничения на максимальное число вызовов функции и возможных значений индексов.

Dmitry Kamzolov, Alexander Gasnikov, Yury Maximov
Computationally Efficient Page Rank Algorithm Exploiting Graph Sparsity Downoad paper
Abstract: В данной работе мы исследуем различные механизмы ранжирование интернет сайтов с точки зрения их вычислительной эффективности. Множество интернет сайтов и ссылок между ними представлено в виде взвешенного графа, вершины которого соответствуют сайтам, а ребра соответствуют ссылкам между сайтами. Рост размеров интернета мотивирует создание новых эффективных алгоритмов. Основной проблемой в задаче ранжирования является огромное количество сайтов, которых нам необходимо отранжировать. Метод, работающий за линейное время от количества сайтов в пространстве размерности 10^8 и более, вычислительно затратен и неэффективен. В работе мы рассматриваем алгоритм основанный на идеях Нестерова по ранжированию веб-страниц на разреженных графах. Ключевая идея метода - использование покомпонентного спуска с 1-нормой для разреженной матрицы. В отличие от градиентного спуска это увеличивает количество шагов алгоритма, но зато каждый шаг делается за маленькое количество арифметических операций. Использование этой идеи позволяет решать большой класс задач ранжирования за логарифмическое по величине веб-графа времени. Цель вычислительного эксперимента - проверка теоретической оценки времени работы алгоритма. В работе показано, что теоретическая оценка количества шагов соответствует эксперименту. Показано, что теоритическая оценка сложности шага алгоритма не соответствует эксперименту из-за особенностей программной реализации. Результат является новым и открывает возможности для дальнейшего улучшения метода.

Ksenia Safina, Georgii Bazykin
Correlated evolution analysis of prokaryotic RNA structures Downoad paper
Abstract: Компенсаторные мутации играют большую роль в эволюции различных РНК структур, позволяя восстанавливать функционально важные взаимодействия, утраченные при мутации. Естественный отбор действует на различные РНК структуры с разной силой, что определяет степень вредности мутации, нарушающей структуру, и скорость возможного компенсаторного перехода. В данной работе были изучены компенсаторные замены в ρ-независимых терминаторах транскрипции бактерии Bacillus subtilis, представляющих собой шпильку на конце мРНК с последующим олигоуридиловым трактом. Мы обнаружили, что терминаторы транскрипции являются высококонсервативными структурами, находящимися под действием сильного естестственного отбора. Переходы между Уотсон-Криковскими парами происходят очень быстро, и предпочтительным промежуточным состоянием в переходах AU ↔ GC является пара GU.

Stepan Denisov, Georgii Bazykin
Correlation between positions and splice site evolution in mammalian genomes Downoad paper
Abstract: Сайты сплайсинга представляют собой короткие последовательности фланкирующие интроны. В данной работе рассматриваются корреляции между силой позиций внутри сайтов сплайсинга. Делается попытка выяснить эволюционные механизмы, приведшие к их наличию.

Valeria Potapova
Covering codes for steganography and ZZW construction Downoad paper
Abstract: We compare steganography systems based on covering codes plus standard coding theory constructions and rather recently proposed ZZW construction.

Ekaterina Yakovleva, Pavel Erofeev
Data-driven Models for Run-to-failure Time Prediction for Aircraft Engines Downoad paper
Abstract: In this paper we consider a problem of run-to-failure time prediction for aircraft engines as a generic prognostic problem arising in the filed of predictive maintenance of complex technical systems. We provide a general problem statement and a framework for approaching such problems. Finally we apply our methodology to the benchmark problem and demonstrate promising prognostic capabilities of the proposed approaches.

Aleksandra Bezmenova, Georgii Bazykin, Alexey Kondrashov
Dependence of negative selection force on demographic characteristics of the species Downoad paper
Abstract: Для действия естественного отбора необходима избыточность размножения организмов. Дисперсия числа потомков на особь получила название "возможности для отбора" (или индекс Кроу). Однако связь между возможностью для отбора и действительным отбором не совсем ясна. Сила отбора характеризуется не дисперсией реального числа потомков, а дисперсией ожидаемого числа потомков, которая определяется генотипом особей. В то же время даже в полностью генетически мономорфной популяции (в которой отбор в идеале должен отсутствовать) в силу случайных причин особи могут приносить разное количество потомков, причем вклад этой случайной составляющей тем больше, чем больше потомков в принципе имеют особи данного вида. Истинную силу отрицательного естественного отбора можно оценить по среднему количеству loss-of-function генов, которое несут особи данного вида. Мы проанализировали 139 транскриптомов 19 видов Metazoa, чтобы исследовать зависимость количества loss-of-function от плодовитости и других демографических характеристик организмов.

Matvei Khoroshkin, Dmitry Rodionov
Diverse strategies for transcriptional control of central carbohydrate metabolism in Bacteria Downoad paper
Abstract: Central carbohydrate metabolism (CCM) combines biochemical reactions allowing acquisition of chemical energy and the biosynthetic precursors and intermediates from catabolized sugars. Most of the enzymes from the CCM pathways including glycolysis, pentose-phosphate pathway, Entner-Doudoroff pathway and the tricarboxylic acid cycle are highly conserved among the bacteria. On the contrary, the mechanisms for transcriptional regulation of CCM pathway genes are variable. For instance, there are at least three described CCM regulators in the Firmicutes phylum (Rex, CcpA, and CggR) and another three known regulators (Crp, Cra, HexR) in Gammaproteobacteria. The variability of known regulators for CCM genes in two bacterial phyla suggests that other novel mechanisms for CCM regulation may exists in other lineages of Bacteria and rises questions on their evolution. Using the comparative genomic approach, we predicted four novel CCM regulators, reconstructed their global regulons, and predicted potential effectors that are CCM intermediates. The PckR, GapR, and GluR regulators are predicted to control CCM genes in three lineages of Alphaproteobacteria (Rhizobiales, Rhodobacterales, and Caulobacterales). The AraQ regulon controls the arabinose utilization and CCM genes in Bifidobacteria. The analysis of evolutionary distributions of the investigated and known CCM regulons provides new insights into the evolution of CCM regulation in Bacteria.

Dmitry Bankov, Evgeny Khorov, Andrey Lyakhov, Alexander Krotov
Efficiency Analysis of the Restricted Access Window for Energy Harvesting Sensor Network Downoad paper
Abstract: В данной работе рассматривается сеть сенсоров, работающих согласно дополнению к стандарту IEEE 802.11ah. Точка доступа периодически выделяет группе сенсоров интервал времени — окно ограниченного доступа — в течение которого они могут отправить данные. В данной работе рассматривается задача рационального выбора длительности окна ограниченного доступа для достижения требуемой вероятности успешной передачи данных. В работе представлена аналитическая модель процесса передачи данных, учитывающая то, что сенсоры обладают ограниченной энергией.

Roman Gershgorin, Konstantin Gorbunov, Alexander Seliverstov, Vassily Lyubetsky
Evolution of Chromosome Structures Downoad paper
Abstract: An effective algorithm to reconstruct chromosomal structures is developed together with its computer implementation. The algorithm is applied to study chromosomal evolution in plastids of the rhodophytic branch and mitochondria of apicomplexan parasites. The chromosomal structure is understood as an arbitrary set of linear and circular chromosomes where each gene is defined by the tail and head; the gene length, nucleotide composition, and intergenic chromosomal regions are not taken into account. We complement the standard operations with the operations of deletion and insertion of a chromosome fragment. The distance between chromosome structures is defined as the minimum total weight of the sequence of operations that transforms one structure into another where operation weights are not necessarily equal; and this sequence is called the shortest. Gene composition is variable, operation weights can be arbitrary and any paralogs are permissible. By our algorithm we solve the following three tasks: (1) finding the distance and the corresponding shortest sequence; (2) finding the matrix of pairwise distances between structures from a given set, and generating the optimal evolutionary tree for the matrix; (3) reconstructing the ancestral structures based on the structures at the tree leaves.

Ekaterina Zhuravleva, Alexander Favorov, Elena Stavrovskaya, Andrew Mironov
Evolutionary and structural patterns of non-coding RNA molecules Downoad paper
Abstract: Некодирующие РНК являются важными функциональными молекулами клетки. Среди этих не транслируемых в белок последовательностей выделяют основные классы: ядерные, малые ядрышковые, микроРНК, длинные некодирующие РНК и регуляторных элементов. Несмотря на широкий спектр выполняемых ими функций, а также большой вклад в изменчивость, объясняемый уникальными функциональными особенностями, эти некодирущие РНК имеют некоторые общие эволюционные закономерности, обусловленные термодинамическими особенностями структуры и её стабильностью. Исследование эволюции элементов вторичной структуры нкРНК является важной задачей с практической точки зрения. Информацию о связи свободной энергии структуры с отбором в различных участках последовательности нкРНК можно, в частности, использовать для улучшения работы ряда алгоритмов по поиску генов нкРНК в геноме. Данная работа посвящена исследованию действия отбора в различных элементах вторичной структуры основных классов нкРНК. В качестве анализируемых организмов рассмотрены плодовые мушки рода Drosophila. В работе были изучены данные по дивергенции и полиморфизму нкРНК, анализ действия отбора был осуществлен при помощи эволюционного теста dN/dS. Для внутривидовых замен (полиморфизмов) в последовательностях был использован алгоритм предсказания эффекта замены на локальный участок структуры RNAsnp. Осуществлен сравнительный анализ силы этого воздействия полиморфизма на состав энергетического ансамбля структур для элементов вторичной структуры и классов нкРНК при различных частотах встречаемости полиморфизма в популяции.

Nataliya Dranenko, Yaroslav Lozinskiy, Vera Halaycheva, Anastasia Kalinina, Olga Bochkareva
Evolutionary history of rearrangements in Yersinia spp Downoad paper
Abstract: Traditional phylogenetic trees construction based on sequence comparison is significantly affected by the extensive horizontal gene flow between strains due to homologous recombination. On the other hand, genome rearrangements are less sensitive to homologous recombination and hence allow for an alternative ap-proach to construction of phylogenetic trees. We applied that alternative approach to Y. pestis, Y. enterocolitica and Y. pseudotubersulosis genomes and compared results to the traditional phylogeny construction model. Such comparison revealed that recombination events are not uniform in time and high recombination frequency seems to be specific for pathogens, e.g. Y. pestis. More over the history of rearrangements corresponding to the phylogeny based on traditional approach turned out to imply many parallel inversions during Y. pestis evolution. From the other hand, there turned out to be many hotspots in genomes that do not allow to define the optimal recombination history using only information about synteny blocks. Analysis of hot spots is expected to provide a valuable contribution to under-standing of evolution mechanisms of considered organisms.

Pavel Mazin
Expression regulation of desiccation-resistance genes in Polypedilum vanderplanki Downoad paper
Abstract: Polypedilum vanderplanki is а striking example of an insect that can survive complete water loss. It's genome and series of dehydration-rehydration transcriptomes, together with genome of P. nubifer (congeneric desiccation-sensitive midge) were recently released. Here we used de novo transcript prediction that allowed as to identify hundreds of new genes, show that up to 53% of genes undergo alternative splicing (AS) and that AS plays a prominent role in desiccation response. Using newly identified TSS positions we have shown that TCTAGAA DNA motif, closely resembled binding site of D. melanogaster heat shock transcription activator (HSTF), is significantly enriched in promoter regions of desiccation-induced genes in P. vanderplanki but not in P. nubifer. Unlike P. nubifer, P. vanderplanki exhibit doubled TCTAGAA motif upstream of HSTF, that is likely explanation of much stronger activation of HSTF in P. vanderplanki compared to P. nubifer under desiccation.

Daria Belyaeva, Mikhail Belyaev
Filterbank EEG classification in riemannian geometry approach Downoad paper
Abstract: Одна из популярных методик в построении интерфейсов «мозг-компьютер» (ИМК) состоит в выделении из данных электроэнцефалограмм (ЭЭГ) различных частотных полос, приблизительно соответствующих так называемым альфа-, бета-, etc. ритмам мозга. Известно, что различные ритмы в мозге соответствуют различным типам мыслительной активности, поэтому для решения задачи классификации имет смысл рассматривать ритмы изолированно друг от друга. С другой стороны, для решения задачи классификации ЭЭГ много информации можно получить из матриц ковариаций данных. Поскольку пространство ковариационных матриц формирует риманово пространство, для их анализа применима риманова геометрия. Но так как многие классические алгоритмы классификации работают только в евклидовом пространстве, используется проекция на касательное пространство риманова многообразия. Цель этой работы - совместить два описанных подхода и оценить их численные результаты в сравнении с другими популярными алгоритмами анализа ЭЭГ.

Semen Leyn, Dmitry Rodionov
Genomic reconstruction of histidine metabolism and regulation in human microbiome Downoad paper
Abstract: Genome-scale mapping and reconstruction of metabolic pathways and transcriptional regulatory networks in taxonomically diverse microbes is one of the critical tasks of microbial genomics. Human microbiota is the complex and dynamic community of commensal, symbiotic and pathogenic microorganisms that are present on and within the human body and has an enormous impact on humans. Here we investigated the histidine biosynthesis, salvage pathways and transcription regulons in reference set of 1143 bacterial genomes out of sequenced consortia of Human Microbiome Project (HMP). Histidine prototrophic and auxotrophic phenotypes were predicted for each studied genome. Reconstruction of transcriptional regulation for histidine metabolic genes revealed putative histidine transporters in the reference HMP genomes.

Victor Kuznetsov, Georgy Slivko-Koltchik, Yuri Panchin
H. megidis - a new model organism for electrophysiological studies of the rhythmic oscillations Downoad paper
Abstract: Rhythmic behaviors are usually controlled by the nervous system, but the defecation program of C. elegans is a distinguished exclusion. About once per minute a signal is generated and propagates through the chain of gut cells recruiting a wave of muscle contractions that cause defecation. All signaling functions of this process are produced by endoderm cells without the participation of the nervous system. The small size of C. elegans cells impairs the use of standard electrophysiological methods. We propose a new model organism H. megidis to overcome this problem. It is closely related to C. elegans, but has a bigger gut cells suitable for electrophysiological studies. Our study demonstrates that intestinal cycling in H. megidis is associated with unusual all-or-none hyper-polarization action potential with a fixed duration of about one minute and a period of up to 15 minutes and amplitude about 60 mV.

Anton Anikin, Nazar Buzun, Pavel Dvurechensky, Alexander Gagloev, Alexander Gasnikov, Andrey Golov, Alexander Gornov, Aydar Gubaydullin, Yury Maximov, Mikhail Mendel, Vladimir Spokoiny
High-Dimensional Undetermined Linear Systems: Numerical Methods and Modeling Assumptions Downoad paper
Abstract: In the paper we consider a problem of recovering the solution of undetermined system of linear inequalities. Such kind of problems frequently arises in transportation research. We discuss some useful modeling assumptions as well as a survey of state of the art numerical methods to solve a problem in a high dimension setting

Ekaterina Khrameeva, Geoffrey Fudenberg, Mikhail Gelfand, Leonid Mirny
History of chromosome rearrangement reflects spatial organization of the yeast chromain Downoad paper
Abstract: Three-dimensional organization of genomes affects critical cellular processes such as transcription, recombination and replication. In interphase nuclei, chromosomes are not positioned randomly but instead adopt preferred conformations. In budding yeast, Drosophila and some other eukaryotes, chromosomes are organized into a Rabl configuration, with centromeres located adjacent to the spindle pole body and telomeres tethered to the nuclear envelope. Here we detected rearrangement events in Saccaromyces sp. using an automatic approach, and observed that recombination occurred more frequently between spatially close regions. Hi-C data for S. cerevisiae showed that regions equally distant from centromeres were frequently in contact with each other. This result is consistent with the Rabl configuration, where chromosomal arms extend from centromeres aligned with each other. Such alignment was also observed between arms of different chromosomes.

Maria Andrianova, Vladimir Seplyarskiy, Maria Logacheva, Anna Klepikova, Aleksey Penin, Georgii Bazykin, Alexey Kondrashov
Identification de novo mutations in highly polymorphic species Downoad paper
Abstract: Rate of spontaneous mutations is a key question of the population genetics. For highly polymorphic species mutation rate could be one possible explanation of hyperdiversity. Using whole-genome resequencing of two parental and seventeen offspring haploid genotypes, we estimate that the mutation rate in highly polymorphic fungi S. commune is rather high, at 2.0×10-8 (95% CI 1.1×10-8 to 3.8×10-8) per nucleotide per generation. We conclude that high mutation rate is one of factors, which play a role in the hyperdiversity of this species.

Kirill Prosvirov, Andrew Mironov, Ruslan Soldatov
Influence of alignment`s errors on prediction of conservative microRNAsites. Downoad paper
Abstract: МикроРНК - малые эндогенные некодирующие РНК, которые связываются комлпиментарно с мРНК, чтобы их пост-транскрипционно репрессировать. Многие сайты связывания (2ой-7ой нуклеотид), особенно расположенные в 3`НТО, преимущественно консервативны. Для их поиска используют сравнительную геномику, в частности её основной инструмент - множественные выравнивания (МВ). Но МВ тоже имеют свойства накапливать ошибки из-за сильной дивергенции между видами. Целью данной работы был подсчет дополнительных сайтов, которые мы потеряли из-за плохого выравнивания, и . Мы ввели понятие L-консервативности. Сайт называется L-консервативными, если все виды имеют сайт связывания микроРНК внутри заданного окна выравнивания в L нуклеотидов. Нами было полученно значительное увеличение количества найденных сайтов при увеличение рамки без потери чувствительности метода поиска. Также проведено сравнение этого прироста со скоростью эволюции 3`НТО и дивергенции видов.

Elena Lopatina, Olga Bochkareva, Marat Kazanov, Anastasia Kalinina
Insights into evolution history of Burkholderia spp Downoad paper
Abstract: Bacteria with multiple chromosomes belong to Actinobacteria, Chloroflexi, Deinococcus-Thermus, Fibrobacteres, Firmicutes, Proteobacteria and Spirochaetes. In our research we consider genus Burkholderia belonging to Betaproteobacteria. Evolution of these bacteria is of great interest because of their multichromosomal genome organization, their species consists of two or three chromosome. We reconstructed translocations between chromosomes. Also we made a reconstruction of events of gain/loss. It was done by two methods for orthologs and synteny blocks. Another important force shaping the genomic evolution is homologous recombination. We identified homologous recombinations in mallei/pseudomallei group.

Swapnil Ahuja
Introduction of a new metric Hit Rate and it's Variation with Scaling on Classification Algorithms Downoad paper
Abstract: This paper aims to introduce a new metric Hit Rate and how it is effected by the introduction of Scaling and also how does scaling effects accuracy of different algorithms and is not always beneficial.To reach our results we have used Python's Machine Learning Library Scikit-learn which is widely popular and to further validate our findings we have taken to completely different datasets from UCI Machine Learning repository.

Sergey Naumenko
Iterative target contig assembler (iTCA) Downoad paper
Abstract: Genome and transcriptome assembly using NGS data are complex computational problems. Traditional de-Brujin graph based assemblers build a graph on kmers and search the longest path on that graph. Sometimes assembler's users are experiencing diffuculties to reconstruct short and similar sequences: alleles, paralogs and isoforms, because the inner logic of an assembler, based on kmers and kmer graph algorithm is not relevant to the biological sense of the sequences. A real sequence of biological value (protein coding gene, for example) exists as a vertex in a dense graph of similar sequences. In the course of molecular evolution sequences are navigating through this graph under the forces of mutation, selection and genetic drift. Here I present the idea of the algorithm which uses this natural process in the course of contig assembly. I propose to reformulate the assembly problem as a search problem in the sequence's space, rather than overlap problem or the longest path problem. The approach has been successfully tested on the problem of orthologous groups reconstruction of tens of closely related species of lake Baikal gammaridae using RNASeq data.

Grigory Sterling, Pavel Prikhodko
Local correlation as a measure of dependence between random variables Downoad paper
Abstract: В работе рассмотрен метод расчета локальной корреляции между произвольными случайными величинами. Получены предельные соотношения. Исследованы свойства локальной корреляции в одномерной и многомерной постановках.

Fedor Goncharov
Methods of Estimation for the Supremum of Gaussian Processes Downoad paper
Abstract: This paper provides a comparison of two standard methods of estimation for the supremum of a Gaussian process. The first method is a well known Dudley's entropy bound, which argues that supremum depends on the ``size'' of parameter set in sense of the covering numbers. The second one is the technique of generic chaining developed by M.Talagrand, which asymptotically gives sharper results. It is shown that in finite-dimensional case of ellipsoids Dudley's entropy bound is sharp up to log-factor of dimension. Also explicit and optimized constants for asymptotic estimations via generic-chaining are found.

Sofya Garushyants, Olga Tsoy, Ignatiy Goryanin
Microbial composition and metabolic potential development in MFCs during wastewater treatment Downoad paper
Abstract: Among proposed green energy technologies, microbial fuel cells (MFCs) hold promise as an efficient and cost-effective solution for global wastewater treatment. Within an MFC, anaerobically respiring microorganisms degrade organic compounds and donate electrons to an external circuit, thereby coupling removal of organics with electrical power production. These systems have proved efficient in laboratory-scale settings, and are now being scaled-up to be applied to the recovery of energy from industrial and municipal wastewaters. Several microbial species that are associated with anode surfaces of MFCs and capable of electron transfer have been identified, such as different species of Geobacter, but the structure of entire electrogenic communities is not well understood. To apply MFC technology to treat real municipal wastewaters such communities have not only to be capable of electricity generation, but are also expected to be capable of efficient biodegradation. To investigate the structure of MFC communities, we performed metagenomic analysis of microbial communities and corresponding anaerobic digester (AD) sludge inocula from two multi-electrode pilot MFC bioreactors of similar design, that successfully treated wastewater from local distilleries and generated electrical power; one in Edinburgh, Scotland (UK), the other in Okinawa, Japan (JP). Additionally, we studied metabolic potential of microbial community for Okinawian MFC, and performed metatranscriptomic analysis.

Elena Kuznetsova, Sergei Usilin, Alina Minkina, Dmitry Nikolaev
Modification of weak classifiers of Viola-Jones machine for multispectral images Downoad paper
Abstract: Предлагается ряд модификаций хаароподобных признаков слабых классификаторов метода Виолы-Джонса, обеспечивающих детектирование образов на изображениях, характеризующихся значительными искажениями яр-костных контрастов с использованием картины направленных краев. Описывается ряд хаароподобных признаков, адаптированных для распознавания объектов на многоканальных изображениях, позволяющих сохранить информацию о характерных распределениях яркости для всех каналов. Приведены результаты вычислительных экспериментов, демонстрирующих преимущества использования предложенных признаков в машине Виолы-Джонса на примерах задач детектирования дорожных конусов на трехканальных изображениях, а также детектирования колес транспортных средств в видеопотоке в режиме реального времени.

Lev Shestakov
New data about an acoustic communication of Acanthoscelides obtectus (Coleoptera: Bruchidae) Downoad paper
Abstract: Многие Bruchidae являются экономически значимыми карантинными вредителями запасов и, как следствие, распространенными модельными объектами. Тем не менее, акустическая коммуникация представителей данного семейства детально не изучалась. Нами впервые изучен репертуар и способы эмиссии сигналов у A. obtectus (Coleoptera: Bruchidae). Обнаружено три основных способа эмиссии сигналов: тремуляция брюшка, удары брюшка о субстрат и вибрация крыльев. У самцов зарегистрированы призывные сигналы и сигналы ухаживания, а у самок - ответный сигнал на призыв самца и сигнал протеста, издаваемый не готовой к копуляции самкой. Нами показано, что сигналы A. obtectus содержат более стабильные (CV=5-12%) и более изменчивые (CV=35-45%) элементы. Частотные характеристики мало варьировали во всех зарегистрированных типах сигналов (CV=5-12%). Кроме того, частотный максимум разных типов сигналов был сходен (1100-1178 Гц). Ранее показано, что частотные характеристики и временные параметры, соответствующие низким уровням ритмической организации (напр., пульсы) сигналы более стабильны, в то время как на высоких уровнях ритмической организации (напр., серии пульсов) изменчивость увеличивается (Gerhardt, Huber, 2002). Наши данные согласуются с этой гипотезой. Кроме того, экспериментально показано, что разработанные нами методы регистрации низкоамплитудных акустических сигналов можно с успехом использовать для выявления и диагностики карантинных объектов, в т.ч. вредителей запасов, которых сложно диагностировать при помощи доступных методов визуального контроля .

Mikhail Schelkunov, Maxim Nuraliev, Aleksey Penin, Maria Logacheva
Nuclear genome changes accompanying a loss of photosynthesis in orchids of genus Epipogium Downoad paper
Abstract: Epipogium aphyllum and Epipogium roseum are orchids notable for their unusual lifestyle, including total loss of photosynthetic ability. Previously they were shown to contain one of the smallest plastid genomes known, with all genes responsible for photosynthesis and related systems being lost. To investigate changes in their nuclear genomes accompanying the loss of photosynthesis we sequenced their transcriptomes. General comparison of Epipogium nuclear genes with orthologs from closely related photosynthetic species reveals a two-fold increase in mutation accumulation rate in Epipogium. The origin of that increase is disputable but it has already been shown to manifest itself in other parasitic plants. Analysis of the gene contents in the transcriptomes of Epipogium suggests the loss of the majority of subsystems associated with photosynthesis.

Ruslan Yusupov, Alexander Krotov, Evgeny Khorov
On Choosing the Parameters of the Restricted Access Window in IEEE 802.11ah Sensor Network Downoad paper
Abstract: Изначально сети Wi-Fi были созданы для обеспечения беспроводного доступа к сети Интернет небольшому количеству устройств. Однако быстрый рост числа устройств, использующих сети Wi-Fi, привёл к возникновению сценариев, когда к одной беспроводной сети Wi-Fi может быть подключено большое число устройств. Для снижения конкуренции при доступе к каналу между этими устройствами, в стандарте IEEE 802.11ah предусмотрено несколько механизмов, один из которых – механизм RAW – предполагает ограничение числа устройств, имеющих доступ к каналу. В этой статье строится аналитическая модель, позволяющая найти пропускную способность сети при использовании механизма RAW, а также рассматривается способ повысить эту пропускную способность без привлечения дополнительных канальных ресурсов.

Elena Egorova
On multimedia digital fingerprinting codes Downoad paper
Abstract: We analyze recently proposed multimedia digital fingerprinting codes and derive first results on a new arising combinatorial problem.

Manfred Schneps-Schneppe, Dmitry Namiot
On the Network Proximity in City-Scale Ubiquitous Systems Downoad paper
Abstract: This paper discusses the city-scale context-aware mobile information system and programming interfaces - CityProximus. Our project is based on the ideas of network proximity. De-facto, network related information is the easiest way for getting context-related information on mobile devices. It lets us replace geo-information in location based services with data about available networks and network nodes. So, in the proposed system user-defined information could be directly associated with existing and specially created network nodes. Later, this information could be delivered to mobile users being in the proximity to the above-mentioned network nodes. In this paper, we discuss the technical aspects of implementation for such system on the city level.

Yury Maximov, Alexander Podkopaev
Optimal Protein Packing by Convex Optimization Downoad paper
Abstract: We consider NP-hard problem of optimal protein packing from convex optimization point of view. In the paper we propose a combination of several techniques to solve the problem.

Andrei Zaika
Orthoscope: a web-application facilitating search for positive selection in orthologous genes Downoad paper
Abstract: Orthoscope is modern web application that combines multiple console applications in an easy to use visual pipeline. A program is built on modern web-framework and is easily scaled to huge amounts of data.

Igor Silin, Maxim Panov
Overview and experimental comparison of graph clustering algorithms Downoad paper
Abstract: Детектирование сообществ или кластеров в графах --- задача, состоящая в нахождении таких групп вершин, внутри которых связей много, а между группами --- мало. Данная задача возникает при анализе больших графов, встречающихся в приложениях. В этой статье мы сравниваем традиционные алгоритмы кластеризации графов как на реальных наборах данных, так и на специально сгенерированных. Сделан акцент на неоднозначности постановки задачи и разнообразии подходов к ее решению. Сравнение проводится с помощью нескольких оценок качества кластеризации, между которыми также отмечаются отличия. Используются как метрики, предполагающие знание истинной кластеризации, так и метрики, оценивающие исключительно качество полученных кластеров. Кроме того, необходимые теоретические сведения об алгоритмах и метриках представлены в компактном виде.

Ruslan Soldatov
Patterns of microRNA biogenesis and expression in the process of Unfolded Protein Response Downoad paper
Abstract: Abnormal protein folding could have a dangerous consequence for a cell and whole organism. Nearly all membrane and secretory proteins fold into endoplasmic reticulum (ER). The overload of newly synthesized unfolded proteins leads to insufficient capacity of ER and triggers global cellular response called unfolded protein response (UPR). UPR have three parallel pathways of response mediated by signal transducers proteins ATF6, PERK and IRE1. UPR mediates short-term attenuation of ER protein loading and long-term increase of ER protein-folding capacity and activation of UPR target genes. Recent researches demonstrated that microRNAs contributes to the regulation of different steps of UPR pathways. Here we profile microRNA and mRNA expression in UPR-stressed and control Jurkat cell line. We report genome-wide downregulation of microRNAs compared to other classes of small RNAs (e.g. snoRNAs, snRNAs and tRNAs), and downregulation of the main proteins constituent microRNA biogenesis pathway. Despite global downregulation, there exists a class of microRNAs with increased expression. MicroRNA fate could be regulated through different kinds of modifications, which are emergence as new layer of regulation of microRNA stability and targeting. Here we observe unique patterns of microRNA 3'-modifications with 40% increased uridinilation and 20% decreased adenylation.

Ksenia Lezhnina, Sergey Naumenko, Georgii Bazykin, Alexey Kondrashov
Permissive synonymous mutations facilitate subsequent nonsynonymous mutations in vertebrate genomes Downoad paper
Abstract: The structure of the genetic code leaves a footprint on the pathways by which adaptation proceeds. Among the 380 amino acid changes, 230 (60 %) cannot be realized through single nucleotide substitutions. For additional 30 (8 %) amino acid changes, only some of the codons of the ancestral amino acid may be converted into the descendant amino acid by a single nucleotide substitution, while the remaining codons would need to obtain a permissive synonymous substitution first. We hypothesized that this inaccessibility of amino acids by a single substitution limits the pace of adaptation. To test this hypothesis, we used the whole-genome comparisons of 100 vertebrate genomes together with the reconstructed nucleotide ancestral states (we focused on closely related species to make this reconstruction unambiguous). We compared the rates of double nucleotide substitutions to those expected if the two nucleotide substitutions were independent events. We find that the number of double substitutions observed at a single phylogenetic branch that involve a permissive synonymous substitution and a subsequent non-synonymous substitution allowed by it is ~3 times higher than expected under independence. These findings suggest that adaptive evolution is limited by the accessibility matrix of amino acids, and reveal a novel major constraint on evolution.

Ilya Zharov, Yuriy Korostelev
Prediction of specific protein-DNA interactions for MerR family of transcription factors Downoad paper
Abstract: Prediction of biopolymer macromolecule interactions from pure sequence data remains a difficult goal in structural bioinformatics. For instance, correlation of sequence substitutions can provide data on transcription factor binding specificity within particular family of transcription factors. Here we apply this approach to subset MerR family of bacterial transcription factors responsible for heavy metal resistance phenotypes. Crystal structures of MerR family proteins in complexes with DNA are used to validate the predictions. We show that correlated and contacting pairs of residues strongly overlap. The degree of this overlap is especially high for the most specific contacts that is amino acid side chain to DNA base hydrogen bonds.

Pavel Shelyakin
Prediction of transcriptional regulation by sigma factors in bacterial genomes with known TSS Downoad paper
Abstract: One of the main mechanisms of regulation of transcription initiation in bacteria is sequence-specific binding of the RNA-polymerase sigma subunit to promoter DNA. Bacterial cells usually encode one major housekeeping sigma subunit and a several alternative sigma subunits that recognize different promoter sequences and allow the cell to adopt its transcriptional programs to changing conditions. A common approach for identification of promoter sequences recognized by specific sigma subunits is positional weight matrices constructed using experimental data and phylogenetic analysis. Here we show that the normalization of such matrices and the use of data about the precise location of the transcription start point improve predic-tion of the sigma subunit that binds to a specific promoter.

Dmitry Sidorchuk, Nuriya Gusamutdinova, Egor Ershov, Ivan Konovalenko
Problem-oriented stereo vision quality evaluation complex Downoad paper
Abstract: В настоящей статье предлагается новый метод оценки алгоритмов стереозрения. Данный метод использует заранее сконструированную сцену и позволяет получить истинную карту глубины, применяя аппарат проективной геометрии. В работе представлен обзор наиболее известных метрик качества карт диспаратности, предложена новая проблемно-ориентированная метрика.

Dmitrii Borisevich, Lyubov Shatalova, Valery Ilinsky
Refining mutations considered pathogenic using benign variants features Downoad paper
Abstract: Important task for modern bioinformatics is prediction of SNPs impact on phenotype and pathogenicity. Predictions require well-established golden standards of benign and pathogenic mutations lists. Sideway features are used to find benign variants, in contrast pathogenic variants are searched using molecular biology methods and then aggregated to databases. However, pathogenic mutations databases are not always uniform which is the result of labile definition of pathogenicity and difference in approaches used by authors. Thus refining of pathogenic variants from databases is required for their usage. We used features that are often used as markers of benign variant: high variant allele frequency in populations, low mutation effect on protein sequence, prediction of low pathogenicity score by different tools - for analysis of pathogenic variants. We build distributions of variants according to these features and discovered mutations considered to be pathogenic but having a high possibility to be benign according to features.

Vita Stepanova, Iakov Davydov, Alex Tonevitsky
Regulation of relative abundance of ribosomal proteins L12 and L10 Downoad paper
Abstract: Bacterial ribosomes contain one molecule of protein L10 and multiple copies of protein L12 which is present in four, six or eight copies depending on the organism. However, how the production of the necessary amounts of proteins L10 and L12 is ensured, is not known. We hypothesize that the stoichiometry is regulated by a feedback regulation loop that involves a hairpin-like mRNA structure in the gene coding for L10 mRNA.

Dmitry Osipov
Robust order statistics-based receiver: complexity issues and performance evaluation Downoad paper
Abstract: In what follows a coded DHA FH OFDMA system employing low complexity order statistic-based robust receiver is considered. In this paper a problem of inner code and reception parameters choice is addressed. It will be demonstrated that even relatively short inner codes can provide desirable probabilistic characteristics and transmission rates.

Anton Kiryanov, Aleksey Kureev
Simulation-based performance evaluation of mechanisms for logical topology building in MANET. Downoad paper
Abstract: Механизм построения логической топологии (МПЛТ) является составной частью многих протоколов маршрутизации и отвечает за установление и закрытие логических соединений между станциями в беспроводной сети. Интеллектуальной начинкой такого механизма является набор событий, по которым принимаются решения об установлении/закрытии соединений. В данной работе рассматривается один из классов МПЛТ, которые принимают решения на основе статистики принятых/потерянных служебных сообщений. При помощи имитационного моделирования проводится исследование эффективности данного класса МПЛТ в смысле удовлетворения требованиям к надежности, стабильности и быстроте открытия соединений.

Aleksandra Galitsyna, Ekaterina Khrameeva, Sergey Ulyanov
Spatial configuration of the alpha-globin gene domain in three cell types of G.gallus Downoad paper
Abstract: Развитие методов определения конформации хромосом позволяет детально изучать взаимодействия участков хроматина в пространстве. Используя метод 5C, мы исследовали организацию области домена альфа-глобиновых генов курицы в трех типах клеток (в лимфоидных клетках, преэритробластах и индуцированных эритробластах), и выяснили, что хроматин организован в топологические домены (ТАДы) и разделяется на два компартмента активного и неактивного хроматина. В компартменте активного хроматина наблюдается более высокая экспрессия генов, а также большее количество меток ChIP-Seq архитектурного белка хроматина CTCF. Границы компартментов проходят по границам ТАДов и сохраняются между типами клеток и при индукции дифференцировки эритробластов. Домен альфа-глобинов расположен в компартменте активного хроматина. Его экспрессия отсутствует в лимфоидных клетках, идет на низком уровне в преэритробластах и на высоком уровне - в индуцированных эритробластах. Получены данные, свидетельствующие в пользу разрыхления хроматина при активации экспрессии генов альфа-глобинов.

Elena Stavrovskaya, Alexander Favorov, Sarah Wheelan, Andrew Mironov
StereoGene: a tool for fast genomewide correlation assessment Downoad paper
Abstract: The modern high-throughput sequencing methods provide massive amounts of genome-focused, DNA-positioned data. This data is often represented as a function of the DNA coordinate (e.g. coverage). The genome- or chromosome-wide correlations between data from different sources may provide information about functional biological interrelation of the investigated features, e.g., transcription and histone modification. The key idea of the correlation studies is that two features that are similarly distributed along a chromosome may be functionally related. The correlation could also be treated as a function on genomic coordinate, and so we can not only assess the interrelations, but also to investigate their localisation inside the genome. Previously, methods of correlation analysis were applied for numerical annotations and some biological results were obtained. But these methods do not allow to analyze positional correlations. The task to compute the spatial correlation was successfully solved only for interval annotations. Here we present StereoGene that is a fast and powerful tool for estimation of correlations. Program implementation StereoGene allow to do analysis of two coverage profiles on human genome in 3-5 minutes. It works with quantitative and qualitative data. The program takes into account shifts of profiles relative to each other and search for correlation in "somewhere around" positions. It allows also to scale and sum profiles and compare profile combinations.

Simon Karpenko, Ivan Konovalenko, Aleksandr Miller, Boris Miller, Dmitry Nikolaev
Stochastic control of UAV on the basis of robust filtering of 3D natural landmarks observations Downoad paper
Abstract: This work considers the tracking of the UAV (unmanned aviation vehicle) on the basis of on-board observations of natural landmarks including azimuth and elevation angles. It is assumed that either UAV's cameras are able to capture the angular position of reference point and to measure the angles of the sight line. Such measurements involve the real position of UAV in implicit form, and therefore some of nonlinear filters such as Extended Kalman filter (EKF) or others must be used in order to implement these measurements for UAV control. Recently it was shown that modified pseudomeasurement method may be used to control UAV on the basis of the observation of reference points assigned along the UAV path in advance. However, the use of such set of points needs the cumbersome recognition procedure with the huge volume of on-board memory. The natural landmarks serving as such reference points which may be determined on-line can significantly reduce the on-board memory and the computational difficulties. The principal difference of this work is the usage of the 3D reference points coordinates which permits to guide the UAV along the path with varying altitude which is extremely important for successful performance of some autonomous missions. One more novelty of this approach is the usage of robust RANSAC taking into account the UAV motion model. The article suggests the estimation and control algorithm for tracking given reference path under external perturbation and noised angular measurements.

Ilya Solomatin, Alexander Ivanov, Evgeny Khorov
Study of simultaneous usage of MCCA and EDCA for CBR flow transmission over noisy channel Downoad paper
Abstract: Механизм MCCA детерминированного доступа к среде, описанный в стандарте IEEE 802.11s сетей Wi-Fi Mesh, может успешно использоваться в таких сетях для передачи данных с высокими требованиями к качеству обслуживания. Этот механизм позволяет любой станции сети Wi-Fi Mesh зарезервировать последовательность периодических интервалов времени, называемых MCCAOP, в течение которых только эта станция имеет право передавать, а станции в ее двухшаговой окрестности — нет. Такой подход защищает передачу данных внутри MCCAOP от коллизий и эффекта скрытых станций, однако не позволяет полность избавиться от ошибок, связанных с интерференцией со стороны станций вне двухшаговой окрестности, а также со случайными помехами в канале. При этом дополнитель- ное время на совершение повторных попыток передач может быть обеспечено как путем резервирования более частых MCCAOP, так и с помощью использования механизма случайного доступа EDCA вне интервалов MCCAOP. В данной работе исследуется одновременное использование механизмов EDCA и MCCA с целью компенсации недостатка времени для повторных попыток передач.

Sergey Korolev, Leonid Zhukov
Supervised Learning for Link Prediction Using Similarity Indices Downoad paper
Abstract: The problem of link prediction gathered a lot of attention in the last few years, arising in different applications ranging from recommendation systems to social networks. In this paper, we will describe the most popular similarity indices, compare their performance in their ability to show links with the highest probability of being removed from initial network and describe the approach that allows to use them to predict missing links using supervised machine learning. We will show the accuracy of prediction of this method on examples of real networks.

Anastasia Kalinina
The distribution of substitutions reflects features of homologous recombination in bacterial species Downoad paper
Abstract: Homologous recombination is the important evolutionary force that drives spreading of beneficial mutations through a population. In previous studies it has been shown that distributions of the number of differences in fixed-size windows for pairwise comparisons of strains may provide insights into the features of the recombination process. This technique has been applied for Escherichia coli, Burkholderia pseudomallei and Streptococcus suis. The shape of the distribution of a number of substitutions depends only on a genetic distance between considered strains and is characteristic for the each species. Two regimes in such distributions are observed in E. coli and P. suis: for vertically inherited segments and for recombined segments. It has been demonstrated that this fact can be applicable for setting thresholds in more sophisticated approaches for detection of recombination events.

Pavel Rybin
The erasure-correcting capabilities of low-complexity decoded H-LDPC code as irregular LDPC code Downoad paper
Abstract: This paper deals with the Low-Density Parity-Check (LDPC) codes with the constituent Hamming codes (H-LDPC codes) and two different iterative erasure-correcting low-complexity decoding algorithms. The first decoding algorithm uses the properties of the constituent Hamming code. The best known lower-bound on the guaranteed corrected erasure fraction for the H-LDPC codes under the first decoding algorithm was obtained in 2009. The second decoding algorithm considers H-LDPC as the irregular LDPC code and uses the well-known erasure-correcting decoding algorithm for LDPC code with constituent single parity-check (SPC) code. The lower-bound on the guaranteed corrected erasure fraction for H-LDPC code under the second decoding algorithm is introduced for the first time in this paper. Numerical results for the lower-bound, obtained in this paper for H-LDPC code under the second decoding algorithm, significantly exceed the numerical results for the best known lower-bounds, obtained previously for H-LDPC code under the first decoding algorithm.

Zoya Chervontseva, Anna Obraztsova, Elena Stavrovskaya
The evolution of 5’ untranslated regions’ structure in Bacilli and Clostridia genomes Downoad paper
Abstract: Некодирующие РНК (нкРНК) участвуют в большом количестве жизненно важных процессов в клетке. Многие функции, выполняемые нкРНК, напрямую связаны с их структурированностью, однако только для малой части последовательностей нкРНК имеются экспериментальные данные о вторичной структуре. В этой работе мы предлагаем новый метод предсказания функционально значимой структурированности, основанный на филогенетическом анализе близкородственных последовательностей.

Vera Mukhina
The position of the plastid ancestor among cyanobacteria Downoad paper
Abstract: Plastids arose through symbiosis between ancient cyanobacterium and common ancestor of plants, green algae, red algae, and glaucophytes from Archaeplastida kingdom. Later, algae from other phyla acquired plastids by secondary endosymbiosis. This study was focused on the search of plastid ancestors among cyanobacterial clades. During coevolution between cyanobacteria and algae most of bacterial genes were lost and the majority of residual genes was transferred to the host nucleus. In this research we analysed proteins of cyanobacterial origin encoded in plastids and nucleus of primary and secondary hosts and compared them with orthologs in modern cyanobacteria.

Andrey Demkiv, Arthur Zalevsky, Andrey Golovin
The prediction of RNA sequences capable to contact with a given protein using Monte Carlo methods Downoad paper
Abstract: Аптамеры - короткие синтетические ДНК или РНК олигонуклеотиды (до 50 нуклеотидов), способные специфично связываться с белками. Сеqчаc существует метод, позволяющий искать аптамеры in vitro, но он имеет ряд недостатков, главным из которых является большая недопредставленность последовательностей, что влечёт за собой потерю возможно более удачных вариантов. Поэтмоу было решено разработать некомбинаторный метод, который позволит искать последовательности нуклеиновых кислот, способных связываться с заданным белком in silico. На данный момент были разработаны алгоритмы поиска области контакта аптамера с белком, нахождение мест связываний азотистых оснований с белком и поиск наиболее энергетически-выгодных оснований для связывания в найденных местах.

German Novikov
The use of methods of finding patterns in sequence of events to predict failures of complex technical systems Downoad paper
Abstract: Анализ редких событий является областью, включающей в себя методы для обнаружения и прогнозирования событий, например вторжений в сеть или отказов двигателя, которые происходят редко, но имеют существенное влияние на систему. Существуют различные методы из области статистики и анализа данных для этой цели. В статье анализируются методы и алгоритмы, которые используются для прогнозирования редких событий в различных системах и их пригодность для конкретной задачи.

Vsevolod Filaretov
Transcription factors involved in flower formation Downoad paper
Abstract: The flower formation transcription factors are a group of proteins which play key roles in establishing Eudicots flowering time, regulation of inflorescence formation and final structure and shape of flowers. We analyze distribution of such proteins across different families of Eudicots.

Evgeny Ponomarev, Anton Grigoryev
Using optical flow for ego-motion estimation. Downoad paper
Abstract: Определение собственного движения камеры - важная задача в компьютерном зрении. В данной работе рассматривается совместное применение алгоритмов нахождения собственного движения (ego-motion estimation) и алгоритмов вычисления оптического потока(optical flow). Производится обзор ряда методов в каждой из составляющих задачи. Для численного сравнения строится метод, использующий алгоритмы нахождения плотного оптического потока с последующим вычислением по нему вращения камеры и уточнением с помощью RANSAC. Приводятся численные результаты его работы.

Georgy Slivko-Koltchik, Victor Kuznetsov, Yuri Panchin
Voltage dependent and intrinsic cellular mechanisms in an ultradian rhythm generator for nematode Downoad paper
Abstract: Central pattern generators (CPGs) are cellular networks or single cells that produce rhythmic patterned outputs in isolation from sensory feedback. Cellular and molecular mechanisms of circadian (about 24 hours) and fast (with period of seconds) rhythms are well studied, while less attention has been paid to ultradian rhythms with shorter periods (minutes to hours). Calcium wave CPG in the nematode gut is a successful biological model for ultradian rhythms studies. Here we show that intestine CPG cycling could be perturbed by shifting gut cells membrane potential, suggesting participation of plasma membrane voltage gated channels. At the same time we demonstrate, that CPG cycling persist in experiments were membrane potential was continuously clamped at steady voltage levels, that excludes the involvement of plasma membrane voltage gated mechanisms by definition. We suggest that two distinct pacemakers, one based on plasma membrane channels and another based on intrinsic calcium release mechanisms coordinate intestinal CPG cycling.