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

A B C D E F G H I K L M N O P R S T U V W Y Z


A

Swapnil Ahuja
Swapnil Ahuja
Introduction of a new metric Hit Rate and it's Variation with Scaling on Classification Algorithms Download 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.

Maria Andrianova
Maria Andrianova, Vladimir Seplyarskiy, Maria Logacheva, Anna Klepikova, Aleksey Penin, Georgii Bazykin, Alexey Kondrashov
Identification de novo mutations in highly polymorphic species Download 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.

Nadezhda Potapova, Maria Andrianova, Georgii Bazykin, Alexey Kondrashov
Accumulation of mutations in nonsense alleles of Drosophila melanogaster Download 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.

Anton Anikin
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 Download 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

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


up

B

Mikhail Babenko
Mikhail Babenko, Nikolay Chervyakov, Nikolay Kucherov, Anastasiia Garianina, Sergey Golikov
The Development of Computation Monitoring System In Cloud Area In Residue Number System Download paper
Abstract: In this paper the modern approaches to homomorphic ciphers creation with the use of residue number system (RNS) are researched. It is shown, that RNS application of homomorthic ciphers allows to create a fully-homomortphic system of information security in cloud area. A homomorphic encryption scheme in RNS, which allows to check computation results on correctness, is proposed. The modeling of the proposed modified homomorphic encryption scheme in RNS has shown that in case of the information processing time increase on average 10\% it becames possible to project reliable systems of cloudy data protection with the given level of safety.

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

Tatiana Krasavina, Dmitry Bankov, Evgeny Khorov
The Study of the Distributed Authentication Control Method Download paper
Abstract: Одной из основных задач разрабатываемого в рамках развития концепции Интернета вещей стандарта IEEE 802.11ah является организация энергоэффективной работы большого числа сенсоров или станций. Количество последних измеряется тысячами в расчете на одну точку доступа. В случаях, когда такой большой группе станций необходимо одновременно обновить подключение к точке доступа, для снижения конкуренции при доступе к среде IEEE 802.11ah предлагает использовать механизмы управления процессом присоединения. Одним из таких является рассматриваемый в данной работе протокол распределенного управления процессом присоединения устройств (Distributed authentication control, DAC). Для исследования эффективности использования данного протокола в сравнении с подключением по обычным механизмам Wi-Fi была построена модель, позволяющая найти распределение времени присоединения устройств. Кроме того, построенная модель позволила определить параметры DAC, минимизирующие время подключения по данному механизму.

Georgii Bazykin
Vladimir Seplyarskiy, Georgii Bazykin
APOBEC induced mutations are strongly enriched in DNA regions replicating as the lagging strand Download paper
Abstract: APOBEC3B, a cytidine deaminase of the APOBEC family, is one of the main factors causing mutations in human cancers1-4. APOBEC3B specifically deaminates cytosines on single stranded DNA (ssDNA)3,5-8. A fraction of the APOBEC3B-induced mutations occur as clusters ('kataegis') in ssDNA produced during reparation of double-stranded breaks (DSBs). However, the properties of the remaining 87% of APOBEC3B induced mutations, specifically, the source of the ssDNA and the genomic distribution, are largely unknown1,3. Our analysis of genomic1,9 and exomic (TCGA) cancer databases demonstrates that the DNA regions which are usually lagging during DNA replication, and therefore temporarily exist as ssDNA10-12, are the major target of APOBEC3B, carrying >33% of dispersed APOBEC3B-induced mutations. Unexpectedly, while methylated cytosine is generally more mutation-prone than non-methylated cytosine, we report that methylation reduces the rate of APOBEC3B-induced mutations by a factor of ~2. Lastly, we show that in cancers with intensive APOBEC3B-induced mutagenesis, there is almost no increase in mutation rates in late replicating regions (contrary to other cancers); as late-replicating regions are depleted in exons, this results in a 1.3-fold higher fraction of mutations falling into exons. This study provides novel insights into the APOBEC3B-induced mutagenesis, and suggests that mutational processes are severely perturbed in genomes of cancers with the APOBEC3B signature.

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

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

Georgii Bazykin
Change of single-position fitness landscapes and its causes Download paper
Abstract: The dimensionality of complete genome-level fitness landscapes is huge, and studying their shape is hard. Arguably, the most basic level of understanding of a fitness landscape concerns distribution of fitnesses of alleles at a small locus, such as the amino acid propensities at a protein site. In the course of evolution, such single-position landscapes can change due to epistasis (changes elsewhere in the genome) or to environmental fluctuations. Several approaches have been proposed to study the rates and properties of such changes. They can be inferred from a range of patterns, such as changes in direction of selection, patterns of divergence, and phylogenetic distributions of homoplasies. These patterns are informative of the changes of amino acid propensities and, indirectly, of the shape of the fitness landscape. Furthermore, they can be used to distinguish between two major possible causes of changes of site-specific fitness landscapes: epistasis or environmental fluctuations, as these mechanisms predict very different dynamics of site-specific fitness landscapes.

Ksenia Lezhnina, Sergey Naumenko, Georgii Bazykin, Alexey Kondrashov
Permissive synonymous mutations facilitate subsequent nonsynonymous mutations in vertebrate genomes Download 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.

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

Maria Andrianova, Vladimir Seplyarskiy, Maria Logacheva, Anna Klepikova, Aleksey Penin, Georgii Bazykin, Alexey Kondrashov
Identification de novo mutations in highly polymorphic species Download 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.

Galya Klink, Georgii Bazykin
Analysis of prevalence of epistasis on the basis of huge phylogenies Download paper
Abstract: Epistatic interactions between amino acid sites shape the site-specific fitness landscapes, affecting the site-specific probabilities of fixations of different amino acids. There is abundant evidence that epistasis has a major role in shaping the evolution of protein sequences; however, it is hard to quantify its contribution. Here, we reconstruct the phylogeny of several mitochondrial proteins from ~3,000 metazoan species, and use this data to obtain high-resolution site-specific distributions of times between points of occurrence of every amino acid observed at each site. We show that substitutions to the same amino acid are clustered on the phylogenetic tree, and that the extent of clustering is higher in conservative sites. Furthermore, substitutions giving rise to amino acids that segregate as minor frequency alleles in the human population are also phylogenetically clustered near the human branch, showing that much of this polymorphism would be deleterious in other species.

Nadezhda Potapova, Maria Andrianova, Georgii Bazykin, Alexey Kondrashov
Accumulation of mutations in nonsense alleles of Drosophila melanogaster Download 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.

Nadezhda Terekhanova, Georgii Bazykin, Ruslan Soldatov, Vladimir Seplyarskiy
Evolution of local mutation rate and its determinants Download paper
Abstract: Knowledge of mutation rate heterogeneity within the human genome is very applicable in genome-wide association studies. Mutation rate variation is known to be associated with the changes of DNA features; however the main portion of it remains unexplained. Here we show that the correlation between human and chimp 1 Mb regions ~95% and becomes ~30 % lower when we compare human mutation rate with mutation rate in the Strepsirrhini clade. Recombination rate and in a lesser extent replication timing and DNase-hypersensitive sites possess the excess of explained variance for mutation rate in regions in which it changed recently. Although, landscapes of genomic features accumulate fewer changes compared with the landscape of the mutation rate, we found that shifts in distributions of genomic features correlate significantly with the changes in the local mutation rate between species in 1 Mb windows. These findings should be taken into account while constructing evolutionary models.

Alexey Bedrintsev
Alexey Bedrintsev, Vladimir Chepyzhov
Design Space Description Using Extremal Ellipsoids Download paper
Abstract: Problems of data set description and outliers detection are solved by constructing optimal ellipsoid. Optimization problems are formulated as convex programming problems using linear matrix inequalities. Proposed method is compared with similar known before methods in terms of two criteria: volume of ellipsoid and the number of points in train data set that lie beyond the ellipsoid.

Andrey Belogaev
Andrey Belogaev, Artem Krasilov, Evgeny Khorov, Andrey Lyakhov
The study of enhanced reservation information dissemination algorithm in Wi-Fi mesh networks Download paper
Abstract: Различные сетевые протоколы генерируют значительный объем служебного трафика, снижая при этом объем канальных ресурсов, доступных для передачи пользовательских данных. В частности, протокол детерминированного доступа к каналу, описанный в стандарте IEEE 802.11, рассылает информацию о зарезервированных станциями временных интервалах. В стандарте предложен новый подход к рассылке информации, основанный на разбиении информационных сообщений о резервированиях на группы. Возникает задача разработки алгоритма управления этими группами, позволяющего минимизировать объем передаваемых служебных сообщений. В представленной ранее работе был предложен простейший алгоритм, который имел существенный недостаток. Располагая изначально все резервирования в одной группе, алгоритм позволял достичь небольшого объема рассылки лишь при достаточно больших временах жизни резервирований. В данной работе представлен улучшенный алгоритм, лишенный указанного недостатка. Разработан математический метод выбора параметров этого алгоритма, позволяющих минимизировать объем рассылки информационных сообщений. Показано, что новый алгоритм позволяет существенно снизить объем рассылки по сравнению с алгоритмом, представленным ранее.

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

Mikhail Belyaev
Pavel Merinov, Mikhail Belyaev
The effects of automatic artifact removal methods on EEG-based classification accuracy Download paper
Abstract: Одна из ключевых задач при создании интерфейсов мозг-компьютер (ИМК) --- это решение задачи классификации электроэнцефалограмм (ЭЭГ), соответствующих, например, воображению различных движений. ЭЭГ может быть существенно искажено артефактами, не связанными с активностью мозга. Как правило, различные методы решения задачи классификации тестируются на данных, полученных в лабораторных условиях, которые позволяют минимизировать влияние артефактов с помощью постановки эксперимента (например, ограничение на мимику и движения тела, запись сигнала с закрытыми глазами). Профессиональные сообщества прогнозируют выход ИМК за пределы лабораторных условий в ближайшее время. Одна из задач, решение которой необходимо для успешного использования технологии ИМК в условиях повседневной жизни, --- это автоматическое удаление артефактов, число которых неизбежно увеличится. Как правило, алгоритмы автоматической очистки ЭЭГ от артефактов оцениваются экспертами с позиции качества удаления артефактов. Вместе с тем остается открытым вопрос, не удаляют ли эти методы вместе с артефактами информацию, существенную для решения задачи классификации. Цель работы состоит в количественной оценке влияния популярных методов автоматической очистки ЭЭГ на качество решения задачи классификации.

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

Egor Krivov, Mikhail Belyaev
Applying dimensionality reduction methods for EEG signal classification Download paper
Abstract: Для появления интерфейса мозг-компьютер, основанного на электроэнцефалографии (ЭЭГ), необходимо создание быстрого и точного классификатора. Многие современные алгоритмы классификации и извлечения признаков из ЭЭГ построены на использовании матриц пространственной ковариации, однако лишь в последние годы появились алгоритмы, учитывающие риманову геометрию этих матриц.Одной из проблем этих методов является высокая размерность пространства признаков. В данной статье предлагается алгоритм снижения размерности ЭЭГ сигнала, который исправляет этот недостаток. Будучи протестированным на двух наборах данных, предложенный алгоритм демонстрирует результаты сопоставимые или же слегка превосходящие результаты как традиционных, так и созданных в последнее время эффективных алгоритмов, позволяя при этом снижать размерность пространства до десятков признаков.

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

Dmitry Bocharov
Dmitry Bocharov, Ivan Koptelov, Elena Kuznetsova
Image-based passes detectors in automatic vehicle classifier Download paper
Abstract: В данной работе рассмотрена задача детекции транспортного средства в видеопотоке методами технического зрения. Кратко описан общий метод функционирования детектора и подробно рассмотрена его важная составляющая - корреляционный детектор наличия объекта. Предложена более устойчивая двухпараметрическая модификация корреляционного детектора объекта для устранения его повышенной чувствительности и частых ложно-положительных срабатываний. Также, в связи с тем, что детектор проездов демонстрирует низкое качество обнаружения жесткой сцепки между транспортными средствами, предложен метод детектирования сцепок, основанный на поиске преимущественно горизонтальных границ. Результаты тестирования модифицированного детектора проездов демонстрируют улучшения детектирования проездов.

Olga Bochkareva
Elena Lopatina, Olga Bochkareva, Marat Kazanov, Anastasia Kalinina
Insights into evolution history of Burkholderia spp Download 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.

Nataliya Dranenko, Yaroslav Lozinskiy, Vera Halaycheva, Anastasia Kalinina, Olga Bochkareva
Evolutionary history of rearrangements in Yersinia spp Download 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.

Dmitrii Borisevich
Dmitrii Borisevich, Lyubov Shatalova, Valery Ilinsky
Refining mutations considered pathogenic using benign variants features Download 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.

Martin Bossert
Mohamed H. Mostafa, Martin Bossert
Combinatorial Metrics and Collaborative Error/Erasure Decoding for Translational Metrics Download paper
Abstract: The combinatorial metric is a huge family of metrics. Metrics such as Hamming, burst and array (criss-cross or cover) metrics are special cases of this metric (translational metrics). The decoding problem in such a metric can be simplified by dividing it into smaller decoding problems in Hamming metric (being the widely used metric). This has been already done for both burst and array metrics. A general form of such simplification can be achieved through graph coloring. Although the coloring problem is NP hard, it has to be solved once per metric. For different combinatorial metrics the same coloring can be used if a certain relation is satisfied. A "novel" method of decoding in translational metrics beyond half the minimum distance using error/erasure decoders is introduced. By exploiting the properties of the metrics, we obtain a gain in the decoding radius but introduce decoding failures, however, with negligible probability.

Nazar Buzun
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 Download 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

Nazar Buzun, Alexandra Suvorikova, Vladimir Spokoiny
Multiscale parametric approach for change point detection Download paper
Abstract: This work presents a novel algorithm for change point detection, that can be applied for analysis of data of unknown nature. It is based on likelihood-ratio test statistics, as its behaviour can be described in terms of \chi^2-distribution even in case of model misspecification. To discover change point in the quickest way, statistics is calculated in a set of running windows of different scales. Algorithm is self-tuned: critical values are justified by data and calculated with multiplier bootstrap procedure. To make the method more robust for outliers, the concept of change-point patterns is presented.

Aleksey Buzmakov
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 Download paper
Abstract: В статье рассматривается влияние применения полихроматического рентгеновского пучка для зондирования в методе рентгеновской томографии на точность реконструкции изображений. Проводится анализ 2-мерного варианта задачи. Для изучения влияния параметров эксперимента на выраженность артефактов численно реализована программа моделирования результатов эксперимента. Предложен критерий численной оценки выраженности артефактов восстановления с точки зрения возможности дальнейшей оценки качества реконструкции. Представлены и обсуждаютсярезультаты применения критерия к модельным расчетам для разных композиций химических элементов.

Victor Prun, Dmitry Nikolaev, Marina Chukalina, Anastasiya Ingacheva, Aleksey Buzmakov
Non-linear Algebraic Reconstruction Technique for Non-Monochromatic Computed Tomography Download paper
Abstract: Рассматривается задача реконструкции компьютерной томографии с существенно немонохроматическим источником излучения. Показывается наличие характерных артефактов, возникающих при использовании обычных монохроматических алгоритмов для восстановления таких синограмм. Предлагается модификация алгебраического метода реконструкции для такого эксперимента. Вместо типично используемых методов борьбы с артефактами в виде регуляризации или фильтрации входных данных, предлагается внести изменения в постановку задачи. Задача восстановления сводится от вычисление функции затухания рентгеновского излучения, к вычислению концентраций заранее ограниченного набора элементов, составляющих исследуемый объект. Для восстановления концентраций предлагается использовать алгебраический метод. Выведен шаг итерации для такой задачи и описан модельный пример.


up

C

Vladimir Chepyzhov
Alexey Bedrintsev, Vladimir Chepyzhov
Design Space Description Using Extremal Ellipsoids Download paper
Abstract: Problems of data set description and outliers detection are solved by constructing optimal ellipsoid. Optimization problems are formulated as convex programming problems using linear matrix inequalities. Proposed method is compared with similar known before methods in terms of two criteria: volume of ellipsoid and the number of points in train data set that lie beyond the ellipsoid.

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

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

Nikolay Chervyakov
Mikhail Babenko, Nikolay Chervyakov, Nikolay Kucherov, Anastasiia Garianina, Sergey Golikov
The Development of Computation Monitoring System In Cloud Area In Residue Number System Download paper
Abstract: In this paper the modern approaches to homomorphic ciphers creation with the use of residue number system (RNS) are researched. It is shown, that RNS application of homomorthic ciphers allows to create a fully-homomortphic system of information security in cloud area. A homomorphic encryption scheme in RNS, which allows to check computation results on correctness, is proposed. The modeling of the proposed modified homomorphic encryption scheme in RNS has shown that in case of the information processing time increase on average 10\% it becames possible to project reliable systems of cloudy data protection with the given level of safety.

Marina Chukalina
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 Download paper
Abstract: В статье рассматривается влияние применения полихроматического рентгеновского пучка для зондирования в методе рентгеновской томографии на точность реконструкции изображений. Проводится анализ 2-мерного варианта задачи. Для изучения влияния параметров эксперимента на выраженность артефактов численно реализована программа моделирования результатов эксперимента. Предложен критерий численной оценки выраженности артефактов восстановления с точки зрения возможности дальнейшей оценки качества реконструкции. Представлены и обсуждаютсярезультаты применения критерия к модельным расчетам для разных композиций химических элементов.

Victor Prun, Dmitry Nikolaev, Marina Chukalina, Anastasiya Ingacheva, Aleksey Buzmakov
Non-linear Algebraic Reconstruction Technique for Non-Monochromatic Computed Tomography Download paper
Abstract: Рассматривается задача реконструкции компьютерной томографии с существенно немонохроматическим источником излучения. Показывается наличие характерных артефактов, возникающих при использовании обычных монохроматических алгоритмов для восстановления таких синограмм. Предлагается модификация алгебраического метода реконструкции для такого эксперимента. Вместо типично используемых методов борьбы с артефактами в виде регуляризации или фильтрации входных данных, предлагается внести изменения в постановку задачи. Задача восстановления сводится от вычисление функции затухания рентгеновского излучения, к вычислению концентраций заранее ограниченного набора элементов, составляющих исследуемый объект. Для восстановления концентраций предлагается использовать алгебраический метод. Выведен шаг итерации для такой задачи и описан модельный пример.


up

D

Iakov Davydov
Vita Stepanova, Iakov Davydov, Alex Tonevitsky
Regulation of relative abundance of ribosomal proteins L12 and L10 Download 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.

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

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

Alexander Derendyaev
Alexander Derendyaev
Traffic Speed Estimation By Mobile Operator Data Download paper
Abstract: A method for estimating the dynamics of urban traffic velocity with the data from the mobile operator is considered. A model allowing to calculate the approximate speed on road sections and to estimate congestion of these sections is proposed. The method is implemented on the GIS platform GeoTime 3. Experimental re-sults for the road network of Moscow city and Moscow region are discussed.

Yulia Dodonova
Dmitry Petrov, Yulia Dodonova, Leonid Zhukov
Differences in Structural Connectomes between Typically Developing and Autism Groups Download paper
Abstract: We study differences in structural connectomes between typically developing and autism spectrum disorders individuals with machine learning techniques using connection weights and network metrics as features. We build linear SVM classifier with accuracy score 0.64 and report 16 features (seven connection weights and nine network node centralities) best distinguishing these two groups.

Dmitry Petrov, Yulia Dodonova, Leonid Zhukov
Comparison of the kernel effectiveness of SVM classifier to distinguish gender based on the structural connectome Download paper
Abstract: Мы решаем задачу различения пола на основе структурных коннектом с помощью метода опорных векторов с 16 различными ядрами и тремя нормировками исходных данных. Для каждого из ядер и для каждой из нормировок мы сравниваем точность классификации с помощью площади под ROC-кривой. Лучшие результаты - 0.77, дают гауссово и полиномиальные ядра на графах длин кратчайших путей на бинаризованных исходных данных.

Dmitry Doronin
Pavel Nekrasov, Denis Fakhriev, Dmitry Doronin
Method for providing QoS for real-time flows in MANET with dynamic TDMA Download paper
Abstract: В работе решается задача обеспечения качества обслуживания потоков реального времени в многошаговой беспроводной самоорганизующейся сети с динамическим TDMA. Задача заключается в разработке метода выбора слотов на маршруте таким образом, чтобы выполнялись ограничения на задержку и вероятность доведения пакета от источника до получателя, и при этом максимизировалась емкость сети, измеряемая в числе одновременно запущенных потоков реального времени с удовлетворительным качеством.

Sergey Dovgal
Sergey Dovgal, Vladimir Spokoiny
Fisher and Wilks Theorems for Likelihood-Based Density Estimation Download paper
Abstract: This paper revisits the local likelihood density estimation approach, introduced by Loader. This method also allows to estimate the derivatives of the density function, and aggregates them in a complex manner to obtain the final estimate. We study properties of the estimate and prove Fisher and Wilks phenomena. The framework of Spokoiny was used to obtain finite-sample bounds for the estimate. We also allow model misspecification and express the error in terms of «model bias».

Nataliya Dranenko
Nataliya Dranenko, Yaroslav Lozinskiy, Vera Halaycheva, Anastasia Kalinina, Olga Bochkareva
Evolutionary history of rearrangements in Yersinia spp Download 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 Dvurechensky
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 Download 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

Pavel Dvurechensky, Alexander Gasnikov
Stochastic Intermediate Gradient Method: Convex and Strongly Convex Cases Download paper
Abstract: In this paper we introduce new methods for convex optimization problems with inexact stochastic oracle. First method is an extension of the intermediate gradient method proposed by Devolder, Glineur and Nesterov for problems with inexact oracle. Our new method can be applied to the problems with composite structure, stochastic inexact oracle and allows using non-Euclidean setup. We prove estimates for mean rate of convergence and probabilities of large deviations from this rate. Also we introduce two modifications of this method for strongly convex problems. For the first modification we prove mean rate of convergence estimates and for the second we prove estimates for large deviations from the mean rate of convergence. All the rates give the complexity estimates for proposed methods which up to multiplicative constant coincide with lower complexity bound for the considered class of convex composite optimization problems with stochastic inexact oracle.

Artem Dyuba
Artem Dyuba, Arthur Zalevsky, Andrey Golovin
Calculated circular dichroism spectra of homo- and heteropolar G-quadruplexes Download 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.


up

E

Kirill Efimov
Kirill Efimov, Vladimir Spokoiny
Smallest accepted method for model selection Download paper
Abstract: This paper presents a method of model selection based on a smallest accepted (SmA) rule: a model is accepted if it is not rejected against any larger model. The final choice is the simplest accepted model. Model comparison is being done by multiple testing. We present oracle results on subset and parameter estimation for the proposed method.

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

Frank Emmert-Streib
Alexey Stupnikov, Frank Emmert-Streib
Robustness of statistical models for Differential Gene Expression of RNA-seq Download paper
Abstract: RNA -seq is an NGS-based technology, that allows to perform various types of transcriptome analysis. During recent years RNA-seq was also widely used for Differential Gene Expression (DGE) analysis. A number of statistical models were suggested to evaluate RNA-seq data for DGE. Robustness, i.e. the difference of analysis' outcome caused by data shifts or perturbations is one of the key characteristics of any computational method. By specifying the data alterations type, different types of robustness' can be defined. We compare the performance of several popular methods for DGE on RNA-seq data, and explore their robustness to simulated altering of RNA-seq experiment parameters.

Pavel Erofeev
Ekaterina Yakovleva, Pavel Erofeev
Data-driven Models for Run-to-failure Time Prediction for Aircraft Engines Download 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.

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

Egor Ershov, Simon Karpenko, Dmitry Nikolaev, Arseniy Terekhin
About accurate assessment of the inaccuracies of the approximation of straight in the fast Hough transform algorithm Download paper
Abstract: В данной работе проведен анализ точности быстрого преобразования Хафа. В этом алгоритме используются аппроксимация прямых дискретными паттернами специального вида, называемыми диадическими прямыми. Предложен явный способ вычисления координат точек данной прямой, а также проведены теоретические и эмпирические оценки ошибки отклонения диадической от идеальной геометрической прямой.


up

F

Denis Fakhriev
Pavel Nekrasov, Denis Fakhriev, Dmitry Doronin
Method for providing QoS for real-time flows in MANET with dynamic TDMA Download paper
Abstract: В работе решается задача обеспечения качества обслуживания потоков реального времени в многошаговой беспроводной самоорганизующейся сети с динамическим TDMA. Задача заключается в разработке метода выбора слотов на маршруте таким образом, чтобы выполнялись ограничения на задержку и вероятность доведения пакета от источника до получателя, и при этом максимизировалась емкость сети, измеряемая в числе одновременно запущенных потоков реального времени с удовлетворительным качеством.

Alexander Favorov
Elena Stavrovskaya, Alexander Favorov, Sarah Wheelan, Andrew Mironov
StereoGene: a tool for fast genomewide correlation assessment Download 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.

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

Alexander Favorov, Vasily Ramensky, Andrew Mironov
Genes that are best friends: rank-backwards-rank normalization of correlation matrix Download paper
Abstract: We analyze recently proposed multimedia digital fingerprint- ing codes and derive first results on a new arising combinatorial problem.

Vsevolod Filaretov
Vsevolod Filaretov
Transcription factors involved in flower formation Download 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.

Alexey Frolov
Alexey Frolov
An Upper Bound on the Minimum Distance of Tail-Biting LDPC Convolutional codes Download paper
Abstract: The minimum distance of tail-biting low-density parity-check convolutional (TB-LDPCC) codes over GF(q) is investigated. An upper bound on the minimum distance of TB-LDPCC codes is derived. An asymptotic analysis of the new bound is done. It is shown that the bound not only improves all the known upper bounds for linear codes at high rates but at some cases lies under the Gilbert-Varshamov bound.

Geoffrey Fudenberg
Ekaterina Khrameeva, Geoffrey Fudenberg, Mikhail Gelfand, Leonid Mirny
History of chromosome rearrangement reflects spatial organization of the yeast chromain Download 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.


up

G

Alexander Gagloev
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 Download 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

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

Anastasiia Garianina
Mikhail Babenko, Nikolay Chervyakov, Nikolay Kucherov, Anastasiia Garianina, Sergey Golikov
The Development of Computation Monitoring System In Cloud Area In Residue Number System Download paper
Abstract: In this paper the modern approaches to homomorphic ciphers creation with the use of residue number system (RNS) are researched. It is shown, that RNS application of homomorthic ciphers allows to create a fully-homomortphic system of information security in cloud area. A homomorphic encryption scheme in RNS, which allows to check computation results on correctness, is proposed. The modeling of the proposed modified homomorphic encryption scheme in RNS has shown that in case of the information processing time increase on average 10\% it becames possible to project reliable systems of cloudy data protection with the given level of safety.

Sofya Garushyants
Sofya Garushyants, Olga Tsoy, Ignatiy Goryanin
Microbial composition and metabolic potential development in MFCs during wastewater treatment Download 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.

Alexander Gasnikov
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 Download 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

Pavel Dvurechensky, Alexander Gasnikov
Stochastic Intermediate Gradient Method: Convex and Strongly Convex Cases Download paper
Abstract: In this paper we introduce new methods for convex optimization problems with inexact stochastic oracle. First method is an extension of the intermediate gradient method proposed by Devolder, Glineur and Nesterov for problems with inexact oracle. Our new method can be applied to the problems with composite structure, stochastic inexact oracle and allows using non-Euclidean setup. We prove estimates for mean rate of convergence and probabilities of large deviations from this rate. Also we introduce two modifications of this method for strongly convex problems. For the first modification we prove mean rate of convergence estimates and for the second we prove estimates for large deviations from the mean rate of convergence. All the rates give the complexity estimates for proposed methods which up to multiplicative constant coincide with lower complexity bound for the considered class of convex composite optimization problems with stochastic inexact oracle.

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

Mikhail Gelfand
Ekaterina Khrameeva, Geoffrey Fudenberg, Mikhail Gelfand, Leonid Mirny
History of chromosome rearrangement reflects spatial organization of the yeast chromain Download 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.

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

Roman Gershgorin
Roman Gershgorin, Konstantin Gorbunov, Alexander Seliverstov, Vassily Lyubetsky
Evolution of Chromosome Structures Download 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.

Sergey Golikov
Mikhail Babenko, Nikolay Chervyakov, Nikolay Kucherov, Anastasiia Garianina, Sergey Golikov
The Development of Computation Monitoring System In Cloud Area In Residue Number System Download paper
Abstract: In this paper the modern approaches to homomorphic ciphers creation with the use of residue number system (RNS) are researched. It is shown, that RNS application of homomorthic ciphers allows to create a fully-homomortphic system of information security in cloud area. A homomorphic encryption scheme in RNS, which allows to check computation results on correctness, is proposed. The modeling of the proposed modified homomorphic encryption scheme in RNS has shown that in case of the information processing time increase on average 10\% it becames possible to project reliable systems of cloudy data protection with the given level of safety.

Andrey Golov
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 Download 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

Andrey Golovin
Artem Dyuba, Arthur Zalevsky, Andrey Golovin
Calculated circular dichroism spectra of homo- and heteropolar G-quadruplexes Download 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.

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

Fedor Goncharov
Fedor Goncharov
Methods of Estimation for the Supremum of Gaussian Processes Download 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.

Konstantin Gorbunov
Roman Gershgorin, Konstantin Gorbunov, Alexander Seliverstov, Vassily Lyubetsky
Evolution of Chromosome Structures Download 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.

Alexander Gornov
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 Download 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

Ignatiy Goryanin
Sofya Garushyants, Olga Tsoy, Ignatiy Goryanin
Microbial composition and metabolic potential development in MFCs during wastewater treatment Download 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.

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

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

Aydar Gubaydullin
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 Download 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

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


up

H

Vera Halaycheva
Nataliya Dranenko, Yaroslav Lozinskiy, Vera Halaycheva, Anastasia Kalinina, Olga Bochkareva
Evolutionary history of rearrangements in Yersinia spp Download 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.

Diyar Jamal Hamad
Diyar Jamal Hamad, Khirota Gorgees Yalda, Ibrahim Taner Okumus
Getting traffic statistics from network devices in an SDN environment using OpenFlow Download paper
Abstract: SDN/OpenFlow network architecture provides a significant advantage over other because it is easier to tune up and introduce new functionalities. Even if many papers focus on the problem of network management, monitoring and control to improve the QoS seen by the customers, only some supply solutions for measuring network performance, e.g., latency, throughput, and packet loss, but our is different by measuring QoS and count byte in each link or port, In terms of network monitoring, OpenFlow allows to build a monitoring solution adjusted to the specific network needs. In this paper, we demonstrate how to use OpenFlow features to get traffic statistics from network devices. In our test environment, collected traffic statistics is used to calculate the available bandwidth on each link in the network. We analyze the effect of statistics collection frequency on the network load and the accuracy of the results collected.


up

I

Dmitrii Ilin
Dmitry Nikolaev, Elena Limonova, Dmitrii Ilin
Improving neural network performance on SIMD architectures Download paper
Abstract: Данная работа посвящена методам ускорения нейросетевого распознавания образов на SIMD архитектурах на примере ARM NEON. Рассмотрен способ ускорения распознавания образов, доступный для ряда современных процессоров: использование SIMD расширений. Описано использование нейронных сетей в задачах распознавания образов, и выделены наиболее трудоемкие операции. Рассмотрены такие методы ускорения матричных вычислений, как использование типа half float и использование целочисленной арифметики. Показан способ векторизации вычислений нелинейных функций активации в нейронных сетях. Приведены экспериментальные результаты ускорения полносвязных и сверточных нейронных сетей на ARM NEON.

Valery Ilinsky
Dmitrii Borisevich, Lyubov Shatalova, Valery Ilinsky
Refining mutations considered pathogenic using benign variants features Download 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.

Anastasiya Ingacheva
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 Download paper
Abstract: В статье рассматривается влияние применения полихроматического рентгеновского пучка для зондирования в методе рентгеновской томографии на точность реконструкции изображений. Проводится анализ 2-мерного варианта задачи. Для изучения влияния параметров эксперимента на выраженность артефактов численно реализована программа моделирования результатов эксперимента. Предложен критерий численной оценки выраженности артефактов восстановления с точки зрения возможности дальнейшей оценки качества реконструкции. Представлены и обсуждаютсярезультаты применения критерия к модельным расчетам для разных композиций химических элементов.

Alexandr Sheshkus, Dmitry Nikolaev, Anastasiya Ingacheva, Natalya Skoryukina
Approach to the recognition of flexible forms on the example of the credit card date recognition Download paper
Abstract: В данной работе рассматривается задача поиска информационных полей документа с гибкой формой на примере распознавания даты окончания срока действия кредитной карты. Обсуждаются принципиальные трудности этой задачи и предлагаются методы ее решения. Рассматриваемая задача решается для случая применения на мобильных устройствах, что накладывает жесткие требования на вычислительную сложность. В работе приводятся результаты формального анализа производительности и точности предложенного алгоритма. Спектр ошибок системы распознавания как целого показывает, что предложенный алгоритм решает задачу с требуемой точностью.

Victor Prun, Dmitry Nikolaev, Marina Chukalina, Anastasiya Ingacheva, Aleksey Buzmakov
Non-linear Algebraic Reconstruction Technique for Non-Monochromatic Computed Tomography Download paper
Abstract: Рассматривается задача реконструкции компьютерной томографии с существенно немонохроматическим источником излучения. Показывается наличие характерных артефактов, возникающих при использовании обычных монохроматических алгоритмов для восстановления таких синограмм. Предлагается модификация алгебраического метода реконструкции для такого эксперимента. Вместо типично используемых методов борьбы с артефактами в виде регуляризации или фильтрации входных данных, предлагается внести изменения в постановку задачи. Задача восстановления сводится от вычисление функции затухания рентгеновского излучения, к вычислению концентраций заранее ограниченного набора элементов, составляющих исследуемый объект. Для восстановления концентраций предлагается использовать алгебраический метод. Выведен шаг итерации для такой задачи и описан модельный пример.

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

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

Alexander Ivanov, Evgeny Khorov, Egor Kuznetsov
Analytical Model of Multicast MCCA-based Streaming in the Presence of Noise Download paper
Abstract: Механизм детерминированного доступа MCCA, описанный в стандарте IEEE 802.11 сетей Wi-Fi, позволяет станциям резервировать интервалы времени для передачи данных. Защита от коллизий и эффекта скрытых станций, обеспечиваемая детерминированным доступом, позволяет использовать MCCA для передачи данных с заданными требованиями к качеству обслуживания. В случае, когда такие данные требуется передать сразу нескольким получателям, MCCA для экономии канальных ресурсов позволяет устанавливать многоадресное резервирование. Однако остается открытым вопрос о выборе параметров таких резервирований. В данной работе предлагается метод определения таких параметров многоадресного резервирования, при которых на каждом из получателей выполнены требования к качеству обслуживания передаваемого потока, а расход канальных ресурсов минимален.

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

Fedor Ivanov
Fedor Ivanov, Igor Zhilin, Victor Zyablov
Erasure Insertion in Generalized Error Locating Codes Download paper
Abstract: In this paper we propose a new method of erasures insertion in first outer code of generalized error locating (GEL) code. This method is based on estimations of probability of inner codes syndromes. These probabilities are used in a threshold obtaining algorithm. An optimization of this algorithm is also considered. Numerical results for suggested algorithm for some signal-noise ratios (SNRs) are presented. These results allow us to conclude that redundancy of first outer code can be significantly decreased (especially for low SNRs) using our proposed procedure.

Igor Zhilin, Fedor Ivanov, Victor Zyablov
Decoding GEL codes under decoding of the outer codes up to the Johnson bound Download paper
Abstract: В данной работе предложен алгоритм декодирования кодов с обобщенной локализацией ошибок (ОЛО-кодов), когда внутренние коды декодируются до границы минимального расстояния, а внешние - до границы Джонсона. На основании данного метода декодирования получена верхняя граница вероятности неправильного декодирования ОЛО-кода и построен алгоритм выбора избыточностей внешних кодов для заданной конструкции кода и входной и выходной вероятностей ошибки. Показано, что максимальная достижимая скорость кодов, оптимизированных для предложенного алгоритма декодирования существенно превосходит скорость кодовых конструкций, оптимизированных для декодирования до границы минимального расстояния.


up

K

Grigory Kabatiansky
Grigory Kabatiansky, Stanislav Kruglik
On codes correcting constant number of errors in l1 metric Download paper
Abstract: We give a number-theoretical construction of codes in l1 (or modular) metric which for the case of fixed number of corrected errors have asymptotically minimal possible redundancy (the same as the corresponding Hamming bound). This construction is based on Bose-Chowla theorem from additive number theory.

Anastasia Kalinina
Elena Lopatina, Olga Bochkareva, Marat Kazanov, Anastasia Kalinina
Insights into evolution history of Burkholderia spp Download 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.

Anastasia Kalinina
The distribution of substitutions reflects features of homologous recombination in bacterial species Download 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.

Nataliya Dranenko, Yaroslav Lozinskiy, Vera Halaycheva, Anastasia Kalinina, Olga Bochkareva
Evolutionary history of rearrangements in Yersinia spp Download 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.

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

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

Simon Karpenko
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 Download 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.

Egor Ershov, Simon Karpenko, Dmitry Nikolaev, Arseniy Terekhin
About accurate assessment of the inaccuracies of the approximation of straight in the fast Hough transform algorithm Download paper
Abstract: В данной работе проведен анализ точности быстрого преобразования Хафа. В этом алгоритме используются аппроксимация прямых дискретными паттернами специального вида, называемыми диадическими прямыми. Предложен явный способ вычисления координат точек данной прямой, а также проведены теоретические и эмпирические оценки ошибки отклонения диадической от идеальной геометрической прямой.

Marat Kazanov
Elena Lopatina, Olga Bochkareva, Marat Kazanov, Anastasia Kalinina
Insights into evolution history of Burkholderia spp Download 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.

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

Anna Kaznadzey
Anna Kaznadzey, Pavel Shelyakin
Co-evolution of carbohydrate metabolism genes of same and different functional classes in bacteria Download 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.

Mark Kelbert
Mark Kelbert, Pavel Mozgunov
Asymptotic analysis of the Renyi, Tsallis and Fisher entropies in a Bayesian problem Download paper
Abstract: Consider a Bayesian problem of estimating of probability of success in a series of trials with binary outcomes. We study the asymptotic behaviour of weighted differential entropy for posterior probability density function (PDF) conditional on x successes after n trials, when n to infinity. Suppose that one is interested to know whether the coin is fair or not and for large n is interested in true frequency. In other words, one wants to emphasize the parameter value p=1/2. To do so the concept of weighted differential entropy introduced in [Belis1968] is used when the frequency gamma is necessary to emphasize. It was found that the weight in suggested form does not change the asymptotic form of Shannon, Renyi, Tsallis and Fisher entropies, but change the constants. The leading term in weighted Fisher Information is changed by some constant which depend on distance between the true frequency and the value we want to emphasize.

Matvei Khoroshkin
Matvei Khoroshkin, Dmitry Rodionov
Diverse strategies for transcriptional control of central carbohydrate metabolism in Bacteria Download 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.

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

Anton Kiryanov, Evgeny Khorov, Andrey Lyakhov
Analytical Model of Multimedia Streaming via Common Periodic Reservations of the Wireless Channel Download paper
Abstract: Для предотвращения коллизий внутри одной беспроводной сети и выполнения требований к качеству обслуживания в сетях Wi-Fi точки доступа (англ.: Access Points, APs), которые выполняют роль координаторов сетей, могут использовать метод HCCA детерминированного доступа к каналу. Однако из-за стремительного роста числа беспроводных сетей часто возникает проблема межсетевой интерференции при совместном использования общего частотно-временного канального ресурса. Для разрешения данной проблемы в дополнении IEEE 802.11aa стандарта Wi-Fi предлагается использовать механизм резервирований HCCA TXOP Negotiation, который позволяет точкам доступа заранее договориться о периодических временных интервалах, в течение которых будет вестись передача данных в каждой из сетей. В данной работе для исследования эффективности такого механизма разрабатывается аналитическая модель, которая позволяет определить параметры зарезервированных интервалов, минимизировать используемый канальный ресурс и выполнить требования к качеству обслуживания передаваемых потоков.

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

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

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

Tatiana Krasavina, Dmitry Bankov, Evgeny Khorov
The Study of the Distributed Authentication Control Method Download paper
Abstract: Одной из основных задач разрабатываемого в рамках развития концепции Интернета вещей стандарта IEEE 802.11ah является организация энергоэффективной работы большого числа сенсоров или станций. Количество последних измеряется тысячами в расчете на одну точку доступа. В случаях, когда такой большой группе станций необходимо одновременно обновить подключение к точке доступа, для снижения конкуренции при доступе к среде IEEE 802.11ah предлагает использовать механизмы управления процессом присоединения. Одним из таких является рассматриваемый в данной работе протокол распределенного управления процессом присоединения устройств (Distributed authentication control, DAC). Для исследования эффективности использования данного протокола в сравнении с подключением по обычным механизмам Wi-Fi была построена модель, позволяющая найти распределение времени присоединения устройств. Кроме того, построенная модель позволила определить параметры DAC, минимизирующие время подключения по данному механизму.

Alexander Ivanov, Evgeny Khorov, Egor Kuznetsov
Analytical Model of Multicast MCCA-based Streaming in the Presence of Noise Download paper
Abstract: Механизм детерминированного доступа MCCA, описанный в стандарте IEEE 802.11 сетей Wi-Fi, позволяет станциям резервировать интервалы времени для передачи данных. Защита от коллизий и эффекта скрытых станций, обеспечиваемая детерминированным доступом, позволяет использовать MCCA для передачи данных с заданными требованиями к качеству обслуживания. В случае, когда такие данные требуется передать сразу нескольким получателям, MCCA для экономии канальных ресурсов позволяет устанавливать многоадресное резервирование. Однако остается открытым вопрос о выборе параметров таких резервирований. В данной работе предлагается метод определения таких параметров многоадресного резервирования, при которых на каждом из получателей выполнены требования к качеству обслуживания передаваемого потока, а расход канальных ресурсов минимален.

Andrey Belogaev, Artem Krasilov, Evgeny Khorov, Andrey Lyakhov
The study of enhanced reservation information dissemination algorithm in Wi-Fi mesh networks Download paper
Abstract: Различные сетевые протоколы генерируют значительный объем служебного трафика, снижая при этом объем канальных ресурсов, доступных для передачи пользовательских данных. В частности, протокол детерминированного доступа к каналу, описанный в стандарте IEEE 802.11, рассылает информацию о зарезервированных станциями временных интервалах. В стандарте предложен новый подход к рассылке информации, основанный на разбиении информационных сообщений о резервированиях на группы. Возникает задача разработки алгоритма управления этими группами, позволяющего минимизировать объем передаваемых служебных сообщений. В представленной ранее работе был предложен простейший алгоритм, который имел существенный недостаток. Располагая изначально все резервирования в одной группе, алгоритм позволял достичь небольшого объема рассылки лишь при достаточно больших временах жизни резервирований. В данной работе представлен улучшенный алгоритм, лишенный указанного недостатка. Разработан математический метод выбора параметров этого алгоритма, позволяющих минимизировать объем рассылки информационных сообщений. Показано, что новый алгоритм позволяет существенно снизить объем рассылки по сравнению с алгоритмом, представленным ранее.

Vyacheslav Loginov, Evgeny Khorov, Andrey Lyakhov
Analytical model of instantaneous packet relaying in the IEEE 802.11ah networks Download paper
Abstract: В настоящее время в мире получила большое распространение концепция Интернета Вещей (англ.: Internet of Things, IoT). Представленные на рынке беспроводные технологии не удовлетворяют требованиям Интернета вещей, связанным, главным образом, с поддерживаемым числом устройств и энергопотреблением. Для выполнения требований IoT в данный момент разрабатывается дополнение к стандарту IEEE 802.11ah, черновик которого уже доступен для изучения. В частности, для увеличения пропускной способности и области покрытие сети, в новом дополнении было предложено использовать ретрансляторы и механизм мгновенной ретрансляции пакетов. В данной работе представлена аналитическая модель передачи данных при использовании механизма мгновенной ретрансляции пакетов в сетях IEEE 802.11ah, позволяющая оценить пропускную способность сети в режиме насыщения.

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

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

Ekaterina Khrameeva, Geoffrey Fudenberg, Mikhail Gelfand, Leonid Mirny
History of chromosome rearrangement reflects spatial organization of the yeast chromain Download 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.

Ekaterina Khrameeva
3D structure of the Drosophila chromatin Download paper
Abstract: We analyze recently proposed multimedia digital fingerprint- ing codes and derive first results on a new arising combinatorial problem.

Stanislav Kikot
Stanislav Kikot
The formulas of the first order which remain with minimal filtering Download paper
Abstract: В этой короткой работе мы даем полное синтаксическое описание формул первого порядка, сохраняющихся при минимальных фильтрациях с точностью до эквивалентности.

Anton Kiryanov
Anton Kiryanov, Evgeny Khorov, Andrey Lyakhov
Analytical Model of Multimedia Streaming via Common Periodic Reservations of the Wireless Channel Download paper
Abstract: Для предотвращения коллизий внутри одной беспроводной сети и выполнения требований к качеству обслуживания в сетях Wi-Fi точки доступа (англ.: Access Points, APs), которые выполняют роль координаторов сетей, могут использовать метод HCCA детерминированного доступа к каналу. Однако из-за стремительного роста числа беспроводных сетей часто возникает проблема межсетевой интерференции при совместном использования общего частотно-временного канального ресурса. Для разрешения данной проблемы в дополнении IEEE 802.11aa стандарта Wi-Fi предлагается использовать механизм резервирований HCCA TXOP Negotiation, который позволяет точкам доступа заранее договориться о периодических временных интервалах, в течение которых будет вестись передача данных в каждой из сетей. В данной работе для исследования эффективности такого механизма разрабатывается аналитическая модель, которая позволяет определить параметры зарезервированных интервалов, минимизировать используемый канальный ресурс и выполнить требования к качеству обслуживания передаваемых потоков.

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

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

Maria Kiselyus
Yury Yanovich, Maria Kiselyus
Generation of random sequences of points with a given density on manifolds Download paper
Abstract: В машинном обучении при построении регрессионных зависимостей или решении задач классификации многомерные описания объектов часто являются избыточными и функционально зависимыми. Такие описания зачастую лежат около многообразий существенно меньшей размерности, чем размерность их первичной записи. Данное предположение называется гипотезой многообразия (Manifold Hypothesis). Использование такой информации может помочь в решении исходной задачи. Так возникает задача оценивания многообразий. В последние годы был разработан ряд подходов, таких как изометрическое отображение (Isomap), локально-линейное вложение (LLE), выравнивания локальных тангенциальных пространств (LTSA) и спектральных вложений Грассмана-Штифеля (GSE), для решения данной задачи. В работе реализован подход для создания генераторов последовательностей случайных величин на многообразиях, основанный на методе выборки с отклонением. Такие последовательности могут быть использованы для тестирования и сравнения алгоритмов оценивания многообразий, а также для тестирования методов оценки плотности на многообразиях. Предложенный подход тестируется для равномерных плотностей на двумерных поверхностях.

Anna Klepikova
Maria Andrianova, Vladimir Seplyarskiy, Maria Logacheva, Anna Klepikova, Aleksey Penin, Georgii Bazykin, Alexey Kondrashov
Identification de novo mutations in highly polymorphic species Download 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.

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

Galya Klink
Galya Klink, Georgii Bazykin
Analysis of prevalence of epistasis on the basis of huge phylogenies Download paper
Abstract: Epistatic interactions between amino acid sites shape the site-specific fitness landscapes, affecting the site-specific probabilities of fixations of different amino acids. There is abundant evidence that epistasis has a major role in shaping the evolution of protein sequences; however, it is hard to quantify its contribution. Here, we reconstruct the phylogeny of several mitochondrial proteins from ~3,000 metazoan species, and use this data to obtain high-resolution site-specific distributions of times between points of occurrence of every amino acid observed at each site. We show that substitutions to the same amino acid are clustered on the phylogenetic tree, and that the extent of clustering is higher in conservative sites. Furthermore, substitutions giving rise to amino acids that segregate as minor frequency alleles in the human population are also phylogenetically clustered near the human branch, showing that much of this polymorphism would be deleterious in other species.

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

Ksenia Lezhnina, Sergey Naumenko, Georgii Bazykin, Alexey Kondrashov
Permissive synonymous mutations facilitate subsequent nonsynonymous mutations in vertebrate genomes Download 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.

Maria Andrianova, Vladimir Seplyarskiy, Maria Logacheva, Anna Klepikova, Aleksey Penin, Georgii Bazykin, Alexey Kondrashov
Identification de novo mutations in highly polymorphic species Download 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.

Nadezhda Potapova, Maria Andrianova, Georgii Bazykin, Alexey Kondrashov
Accumulation of mutations in nonsense alleles of Drosophila melanogaster Download 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.

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

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

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 Download 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.

Ivan Koptelov
Dmitry Bocharov, Ivan Koptelov, Elena Kuznetsova
Image-based passes detectors in automatic vehicle classifier Download paper
Abstract: В данной работе рассмотрена задача детекции транспортного средства в видеопотоке методами технического зрения. Кратко описан общий метод функционирования детектора и подробно рассмотрена его важная составляющая - корреляционный детектор наличия объекта. Предложена более устойчивая двухпараметрическая модификация корреляционного детектора объекта для устранения его повышенной чувствительности и частых ложно-положительных срабатываний. Также, в связи с тем, что детектор проездов демонстрирует низкое качество обнаружения жесткой сцепки между транспортными средствами, предложен метод детектирования сцепок, основанный на поиске преимущественно горизонтальных границ. Результаты тестирования модифицированного детектора проездов демонстрируют улучшения детектирования проездов.

Semen Korolev
Semen Korolev, Oleg Zverkov, Sergei Lyzhin, Alexander Seliverstov, Vassily Lyubetsky
A Search for Genes Encoding Histidine-Containing Leader Peptides in Actinobacteria Download 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.

Sergey Korolev
Sergey Korolev, Leonid Zhukov
Supervised Learning for Link Prediction Using Similarity Indices Download 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.

Yuriy Korostelev
Ilya Zharov, Yuriy Korostelev
Prediction of specific protein-DNA interactions for MerR family of transcription factors Download 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.

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

Tatiana Krasavina
Tatiana Krasavina, Dmitry Bankov, Evgeny Khorov
The Study of the Distributed Authentication Control Method Download paper
Abstract: Одной из основных задач разрабатываемого в рамках развития концепции Интернета вещей стандарта IEEE 802.11ah является организация энергоэффективной работы большого числа сенсоров или станций. Количество последних измеряется тысячами в расчете на одну точку доступа. В случаях, когда такой большой группе станций необходимо одновременно обновить подключение к точке доступа, для снижения конкуренции при доступе к среде IEEE 802.11ah предлагает использовать механизмы управления процессом присоединения. Одним из таких является рассматриваемый в данной работе протокол распределенного управления процессом присоединения устройств (Distributed authentication control, DAC). Для исследования эффективности использования данного протокола в сравнении с подключением по обычным механизмам Wi-Fi была построена модель, позволяющая найти распределение времени присоединения устройств. Кроме того, построенная модель позволила определить параметры DAC, минимизирующие время подключения по данному механизму.

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

Andrey Belogaev, Artem Krasilov, Evgeny Khorov, Andrey Lyakhov
The study of enhanced reservation information dissemination algorithm in Wi-Fi mesh networks Download paper
Abstract: Различные сетевые протоколы генерируют значительный объем служебного трафика, снижая при этом объем канальных ресурсов, доступных для передачи пользовательских данных. В частности, протокол детерминированного доступа к каналу, описанный в стандарте IEEE 802.11, рассылает информацию о зарезервированных станциями временных интервалах. В стандарте предложен новый подход к рассылке информации, основанный на разбиении информационных сообщений о резервированиях на группы. Возникает задача разработки алгоритма управления этими группами, позволяющего минимизировать объем передаваемых служебных сообщений. В представленной ранее работе был предложен простейший алгоритм, который имел существенный недостаток. Располагая изначально все резервирования в одной группе, алгоритм позволял достичь небольшого объема рассылки лишь при достаточно больших временах жизни резервирований. В данной работе представлен улучшенный алгоритм, лишенный указанного недостатка. Разработан математический метод выбора параметров этого алгоритма, позволяющих минимизировать объем рассылки информационных сообщений. Показано, что новый алгоритм позволяет существенно снизить объем рассылки по сравнению с алгоритмом, представленным ранее.

Alexey Kreshchuk
Alexey Kreshchuk, Victor Zyablov
An upper bound on symbol error rate of generalized error-locator codes for symmetric channels Download paper
Abstract: There are some upper bounds on the frame error rate of the generalized error locator codes. The specifics of symmetric channels can be used to improve these bound and also introduce a bound on undetected error probability. We constructed these bound and derived a bound on symbol error rate from them. To do so we have investigated two kinds of symbol errors. The first kind include the errors that occur because of early exit from the decoder. The second kind includes the errors introduced by the erroneous decoding of an outer code. In this work we have introduced bounds on the rates of each of these kinds of symbol errors.

Egor Krivov
Egor Krivov, Mikhail Belyaev
Applying dimensionality reduction methods for EEG signal classification Download paper
Abstract: Для появления интерфейса мозг-компьютер, основанного на электроэнцефалографии (ЭЭГ), необходимо создание быстрого и точного классификатора. Многие современные алгоритмы классификации и извлечения признаков из ЭЭГ построены на использовании матриц пространственной ковариации, однако лишь в последние годы появились алгоритмы, учитывающие риманову геометрию этих матриц.Одной из проблем этих методов является высокая размерность пространства признаков. В данной статье предлагается алгоритм снижения размерности ЭЭГ сигнала, который исправляет этот недостаток. Будучи протестированным на двух наборах данных, предложенный алгоритм демонстрирует результаты сопоставимые или же слегка превосходящие результаты как традиционных, так и созданных в последнее время эффективных алгоритмов, позволяя при этом снижать размерность пространства до десятков признаков.

Alexey Kroshnin
Alexey Kroshnin
The convergence of baricentro for Monge-Kantorovich metrics in one dimensional case with a convex price function Download paper
Abstract: В статье рассмотрена задача Монжа-Канторовича в одномерном случае с выпуклой ценовой функцией. Найден явный вид ее решения. Найден явный вид барицентра конечного набора мер. Для пространства мер с компактным носителем и метрикой Монжа-Канторовича определен барицентр распределения и найдена явная формула для него. Также доказан аналог ЗБЧ для пространства мер с компактным носителем.

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

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

Stanislav Kruglik
Grigory Kabatiansky, Stanislav Kruglik
On codes correcting constant number of errors in l1 metric Download paper
Abstract: We give a number-theoretical construction of codes in l1 (or modular) metric which for the case of fixed number of corrected errors have asymptotically minimal possible redundancy (the same as the corresponding Hamming bound). This construction is based on Bose-Chowla theorem from additive number theory.

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

Nikolay Kucherov
Mikhail Babenko, Nikolay Chervyakov, Nikolay Kucherov, Anastasiia Garianina, Sergey Golikov
The Development of Computation Monitoring System In Cloud Area In Residue Number System Download paper
Abstract: In this paper the modern approaches to homomorphic ciphers creation with the use of residue number system (RNS) are researched. It is shown, that RNS application of homomorthic ciphers allows to create a fully-homomortphic system of information security in cloud area. A homomorphic encryption scheme in RNS, which allows to check computation results on correctness, is proposed. The modeling of the proposed modified homomorphic encryption scheme in RNS has shown that in case of the information processing time increase on average 10\% it becames possible to project reliable systems of cloudy data protection with the given level of safety.

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

Yerbol Kurmangaliyev
Yerbol Kurmangaliyev
RNA-editing quantitative trait loci in humans and fruit flies Download paper
Abstract: ADAR-mediated adenosine deamination (A-to-I editing) is the most common type of RNA editing in metazoans. RNA editing usually affects only a fraction of all transcripts and the level of editing may vary strongly among particular A-to-I sites. In this study, we investigated genotype-specific changes in editing patterns of particular ADAR targets. We used matching genomic and transcriptomic data from multiple individuals to map single nucleotide polymorphisms (SNPs) associated with genotype-specific changes in editing.

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

Dmitry Bocharov, Ivan Koptelov, Elena Kuznetsova
Image-based passes detectors in automatic vehicle classifier Download paper
Abstract: В данной работе рассмотрена задача детекции транспортного средства в видеопотоке методами технического зрения. Кратко описан общий метод функционирования детектора и подробно рассмотрена его важная составляющая - корреляционный детектор наличия объекта. Предложена более устойчивая двухпараметрическая модификация корреляционного детектора объекта для устранения его повышенной чувствительности и частых ложно-положительных срабатываний. Также, в связи с тем, что детектор проездов демонстрирует низкое качество обнаружения жесткой сцепки между транспортными средствами, предложен метод детектирования сцепок, основанный на поиске преимущественно горизонтальных границ. Результаты тестирования модифицированного детектора проездов демонстрируют улучшения детектирования проездов.

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

Egor Kuznetsov
Alexander Ivanov, Evgeny Khorov, Egor Kuznetsov
Analytical Model of Multicast MCCA-based Streaming in the Presence of Noise Download paper
Abstract: Механизм детерминированного доступа MCCA, описанный в стандарте IEEE 802.11 сетей Wi-Fi, позволяет станциям резервировать интервалы времени для передачи данных. Защита от коллизий и эффекта скрытых станций, обеспечиваемая детерминированным доступом, позволяет использовать MCCA для передачи данных с заданными требованиями к качеству обслуживания. В случае, когда такие данные требуется передать сразу нескольким получателям, MCCA для экономии канальных ресурсов позволяет устанавливать многоадресное резервирование. Однако остается открытым вопрос о выборе параметров таких резервирований. В данной работе предлагается метод определения таких параметров многоадресного резервирования, при которых на каждом из получателей выполнены требования к качеству обслуживания передаваемого потока, а расход канальных ресурсов минимален.

Victor Kuznetsov
Victor Kuznetsov, Georgy Slivko-Koltchik, Yuri Panchin
H. megidis - a new model organism for electrophysiological studies of the rhythmic oscillations Download 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.

Georgy Slivko-Koltchik, Victor Kuznetsov, Yuri Panchin
Voltage dependent and intrinsic cellular mechanisms in an ultradian rhythm generator for nematode Download 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.


up

L

Victoria Lavrova
Victoria Lavrova
Cortical evocek responses to cardiac activity in the sleep-wake cycle Download paper
Abstract: Согласно висцеральной теории сна (Пигарев, 2013), сенсорные зоны коры головного мозга, участвующие в анализе экстероцептивной информации в бодрствовании, во сне переключаются на анализ интероцептивной информации. В данной работе проверяли гипотезу согласно которой сердечная деятельность также отражается в активности сенсорных зон коры головного мозга в цикле сон-бодрствование, и пытались локализовать корковые отделы обработки информации, поступающей от сердца. Работу проводили на двух взрослых кошках, у которых записывали ЭЭГ лобной и затылочной областей коры головного мозга. Параллельно регистрировали электрокардиограмму, движения глаз и ритм дыхания . Были проанализированы записи длительностью 4-6 часов, включающие периоды бодрствования, медленноволнового и быстрого сна. Было обнаружено, что сердечная деятельность действительно отражается в электрической активности лобных отделов мозга. При этом связь между сердцем и корковыми областями проявляется во сне и отсутствует в периоды бодрствования. Это наблюдение служит еще одним аргументом в пользу висцеральной теории сна.

Semen Leyn
Semen Leyn, Dmitry Rodionov
Genomic reconstruction of histidine metabolism and regulation in human microbiome Download 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.

Ksenia Lezhnina
Ksenia Lezhnina, Sergey Naumenko, Georgii Bazykin, Alexey Kondrashov
Permissive synonymous mutations facilitate subsequent nonsynonymous mutations in vertebrate genomes Download 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.

Elena Limonova
Dmitry Nikolaev, Elena Limonova, Dmitrii Ilin
Improving neural network performance on SIMD architectures Download paper
Abstract: Данная работа посвящена методам ускорения нейросетевого распознавания образов на SIMD архитектурах на примере ARM NEON. Рассмотрен способ ускорения распознавания образов, доступный для ряда современных процессоров: использование SIMD расширений. Описано использование нейронных сетей в задачах распознавания образов, и выделены наиболее трудоемкие операции. Рассмотрены такие методы ускорения матричных вычислений, как использование типа half float и использование целочисленной арифметики. Показан способ векторизации вычислений нелинейных функций активации в нейронных сетях. Приведены экспериментальные результаты ускорения полносвязных и сверточных нейронных сетей на ARM NEON.

Maria Logacheva
Mikhail Schelkunov, Maxim Nuraliev, Aleksey Penin, Maria Logacheva
Nuclear genome changes accompanying a loss of photosynthesis in orchids of genus Epipogium Download 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.

Maria Andrianova, Vladimir Seplyarskiy, Maria Logacheva, Anna Klepikova, Aleksey Penin, Georgii Bazykin, Alexey Kondrashov
Identification de novo mutations in highly polymorphic species Download 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.

Vyacheslav Loginov
Vyacheslav Loginov, Evgeny Khorov, Andrey Lyakhov
Analytical model of instantaneous packet relaying in the IEEE 802.11ah networks Download paper
Abstract: В настоящее время в мире получила большое распространение концепция Интернета Вещей (англ.: Internet of Things, IoT). Представленные на рынке беспроводные технологии не удовлетворяют требованиям Интернета вещей, связанным, главным образом, с поддерживаемым числом устройств и энергопотреблением. Для выполнения требований IoT в данный момент разрабатывается дополнение к стандарту IEEE 802.11ah, черновик которого уже доступен для изучения. В частности, для увеличения пропускной способности и области покрытие сети, в новом дополнении было предложено использовать ретрансляторы и механизм мгновенной ретрансляции пакетов. В данной работе представлена аналитическая модель передачи данных при использовании механизма мгновенной ретрансляции пакетов в сетях IEEE 802.11ah, позволяющая оценить пропускную способность сети в режиме насыщения.

Elena Lopatina
Elena Lopatina, Olga Bochkareva, Marat Kazanov, Anastasia Kalinina
Insights into evolution history of Burkholderia spp Download 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.

Yaroslav Lozinskiy
Nataliya Dranenko, Yaroslav Lozinskiy, Vera Halaycheva, Anastasia Kalinina, Olga Bochkareva
Evolutionary history of rearrangements in Yersinia spp Download 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.

Andrey Lyakhov
Anton Kiryanov, Evgeny Khorov, Andrey Lyakhov
Analytical Model of Multimedia Streaming via Common Periodic Reservations of the Wireless Channel Download paper
Abstract: Для предотвращения коллизий внутри одной беспроводной сети и выполнения требований к качеству обслуживания в сетях Wi-Fi точки доступа (англ.: Access Points, APs), которые выполняют роль координаторов сетей, могут использовать метод HCCA детерминированного доступа к каналу. Однако из-за стремительного роста числа беспроводных сетей часто возникает проблема межсетевой интерференции при совместном использования общего частотно-временного канального ресурса. Для разрешения данной проблемы в дополнении IEEE 802.11aa стандарта Wi-Fi предлагается использовать механизм резервирований HCCA TXOP Negotiation, который позволяет точкам доступа заранее договориться о периодических временных интервалах, в течение которых будет вестись передача данных в каждой из сетей. В данной работе для исследования эффективности такого механизма разрабатывается аналитическая модель, которая позволяет определить параметры зарезервированных интервалов, минимизировать используемый канальный ресурс и выполнить требования к качеству обслуживания передаваемых потоков.

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

Andrey Belogaev, Artem Krasilov, Evgeny Khorov, Andrey Lyakhov
The study of enhanced reservation information dissemination algorithm in Wi-Fi mesh networks Download paper
Abstract: Различные сетевые протоколы генерируют значительный объем служебного трафика, снижая при этом объем канальных ресурсов, доступных для передачи пользовательских данных. В частности, протокол детерминированного доступа к каналу, описанный в стандарте IEEE 802.11, рассылает информацию о зарезервированных станциями временных интервалах. В стандарте предложен новый подход к рассылке информации, основанный на разбиении информационных сообщений о резервированиях на группы. Возникает задача разработки алгоритма управления этими группами, позволяющего минимизировать объем передаваемых служебных сообщений. В представленной ранее работе был предложен простейший алгоритм, который имел существенный недостаток. Располагая изначально все резервирования в одной группе, алгоритм позволял достичь небольшого объема рассылки лишь при достаточно больших временах жизни резервирований. В данной работе представлен улучшенный алгоритм, лишенный указанного недостатка. Разработан математический метод выбора параметров этого алгоритма, позволяющих минимизировать объем рассылки информационных сообщений. Показано, что новый алгоритм позволяет существенно снизить объем рассылки по сравнению с алгоритмом, представленным ранее.

Vyacheslav Loginov, Evgeny Khorov, Andrey Lyakhov
Analytical model of instantaneous packet relaying in the IEEE 802.11ah networks Download paper
Abstract: В настоящее время в мире получила большое распространение концепция Интернета Вещей (англ.: Internet of Things, IoT). Представленные на рынке беспроводные технологии не удовлетворяют требованиям Интернета вещей, связанным, главным образом, с поддерживаемым числом устройств и энергопотреблением. Для выполнения требований IoT в данный момент разрабатывается дополнение к стандарту IEEE 802.11ah, черновик которого уже доступен для изучения. В частности, для увеличения пропускной способности и области покрытие сети, в новом дополнении было предложено использовать ретрансляторы и механизм мгновенной ретрансляции пакетов. В данной работе представлена аналитическая модель передачи данных при использовании механизма мгновенной ретрансляции пакетов в сетях IEEE 802.11ah, позволяющая оценить пропускную способность сети в режиме насыщения.

Vassily Lyubetsky
Semen Korolev, Oleg Zverkov, Sergei Lyzhin, Alexander Seliverstov, Vassily Lyubetsky
A Search for Genes Encoding Histidine-Containing Leader Peptides in Actinobacteria Download 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.

Roman Gershgorin, Konstantin Gorbunov, Alexander Seliverstov, Vassily Lyubetsky
Evolution of Chromosome Structures Download 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.

Sergei Lyzhin
Semen Korolev, Oleg Zverkov, Sergei Lyzhin, Alexander Seliverstov, Vassily Lyubetsky
A Search for Genes Encoding Histidine-Containing Leader Peptides in Actinobacteria Download 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.


up

M

Sergey Makarychev
Ilya Vyugin, Sergey Makarychev
On the number of solutions of polynomial equation over F_p Download paper
Abstract: We present a new proof of Corvaja and Zannier an upper bound of the number of solutions (x,y) of a polynomial equation P(x,y)=0 over a field F_p, in the case, where x in g_1G, y in g_2G , g_1G, g_2G are cosets by some subgroup G of a multiplicative group F_p*. Some applications of this bound to hyperelliptic curves and additive energies are obtained.

Nina Malayr
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 Download paper
Abstract: Цель настоящей работы - анализ кинематики подъема на ступеньку у подростков с диагнозом Ранний Детский Аутизм (РДА) и анализ кинематики спуска со ступеньки у детей и подростков с РДА в сравнении со здоровыми детьми и подростками. Ранее нами был изучен процесс подъема на ступеньку больных детей. В настоящем исследовании получено, что, также как и у детей с РДА, у больных подростков при подготовке к подъему наблюдались значительно большие колебания амплитуды угловой скорости тазобедренного сустава в сагиттальной плоскости, чем у здоровых ровесников: в 14% проб у подростков с РДА основному минимуму угловой скорости тазобедренного сустава предшествовал, по крайней мере, еще один минимум, с амплитудой ниже порогового. Среди здоровых подростков данное явление было замечено в 5% проб. Однако при анализе процесса спуска данная тенденция сохранялась только в случае сравнения больных и здоровых подростков (дополнительные минимумы в 50% и 15% проб соответственно), а у здоровых детей дополнительные пики наблюдались чаще, чем у больных (16% и 6% соответственно). Также было обнаружено, что при спуске больные подростки меньше разгибали голеностопный сустав, чем их здоровые сверстники, чего не отмечалось во время подъема. Этих различий в изменении голеностопного угла между больными и здоровыми детьми, как при спуске, так и при подъеме не отмечалось. Мы предполагаем, что возрастные особенности кинематики целевого движения ногой при постановке ее на опору при подъеме и спуске дают представление о развитии позного контроля больных РДА, в частности, свидетельствуют об ухудшенной координации больных подростков по сравнению с больными детьми и здоровыми ровесниками.

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

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

Elena Maximova
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 Download paper
Abstract: Цель настоящей работы - анализ кинематики подъема на ступеньку у подростков с диагнозом Ранний Детский Аутизм (РДА) и анализ кинематики спуска со ступеньки у детей и подростков с РДА в сравнении со здоровыми детьми и подростками. Ранее нами был изучен процесс подъема на ступеньку больных детей. В настоящем исследовании получено, что, также как и у детей с РДА, у больных подростков при подготовке к подъему наблюдались значительно большие колебания амплитуды угловой скорости тазобедренного сустава в сагиттальной плоскости, чем у здоровых ровесников: в 14% проб у подростков с РДА основному минимуму угловой скорости тазобедренного сустава предшествовал, по крайней мере, еще один минимум, с амплитудой ниже порогового. Среди здоровых подростков данное явление было замечено в 5% проб. Однако при анализе процесса спуска данная тенденция сохранялась только в случае сравнения больных и здоровых подростков (дополнительные минимумы в 50% и 15% проб соответственно), а у здоровых детей дополнительные пики наблюдались чаще, чем у больных (16% и 6% соответственно). Также было обнаружено, что при спуске больные подростки меньше разгибали голеностопный сустав, чем их здоровые сверстники, чего не отмечалось во время подъема. Этих различий в изменении голеностопного угла между больными и здоровыми детьми, как при спуске, так и при подъеме не отмечалось. Мы предполагаем, что возрастные особенности кинематики целевого движения ногой при постановке ее на опору при подъеме и спуске дают представление о развитии позного контроля больных РДА, в частности, свидетельствуют об ухудшенной координации больных подростков по сравнению с больными детьми и здоровыми ровесниками.

Yury Maximov
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 Download 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

Daria Reshetova, Yury Maximov
Generalization bound for multiclass classifiers Download paper
Abstract: Рассматривается задача многоклассовой классификации. Для нее приводится верхняя оценка радемахеровской сложности множества многоклассовых классификаторов, основанных на минимизации суммарного отступа объектов, и оценки их обобщающей ошибки. Существенно то, что данные оценки приводятся без дополнительных предположений на распределение данных и множество классификаторов.

Yury Maximov, Alexander Podkopaev
Optimal Protein Packing by Convex Optimization Download 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.

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

Pavel Mazin
Pavel Mazin
Expression regulation of desiccation-resistance genes in Polypedilum vanderplanki Download 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.

Mikhail Mendel
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 Download 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

Pavel Merinov
Pavel Merinov, Mikhail Belyaev
The effects of automatic artifact removal methods on EEG-based classification accuracy Download paper
Abstract: Одна из ключевых задач при создании интерфейсов мозг-компьютер (ИМК) --- это решение задачи классификации электроэнцефалограмм (ЭЭГ), соответствующих, например, воображению различных движений. ЭЭГ может быть существенно искажено артефактами, не связанными с активностью мозга. Как правило, различные методы решения задачи классификации тестируются на данных, полученных в лабораторных условиях, которые позволяют минимизировать влияние артефактов с помощью постановки эксперимента (например, ограничение на мимику и движения тела, запись сигнала с закрытыми глазами). Профессиональные сообщества прогнозируют выход ИМК за пределы лабораторных условий в ближайшее время. Одна из задач, решение которой необходимо для успешного использования технологии ИМК в условиях повседневной жизни, --- это автоматическое удаление артефактов, число которых неизбежно увеличится. Как правило, алгоритмы автоматической очистки ЭЭГ от артефактов оцениваются экспертами с позиции качества удаления артефактов. Вместе с тем остается открытым вопрос, не удаляют ли эти методы вместе с артефактами информацию, существенную для решения задачи классификации. Цель работы состоит в количественной оценке влияния популярных методов автоматической очистки ЭЭГ на качество решения задачи классификации.

Aleksandr Miller
Alexey Popov, Aleksandr Miller, Boris Miller, Karen Stepanyan
Application of the Optical Flow as a Navigation Means for UAV Download paper
Abstract: Recently, relatively small and even micro unmanned aerial vehicles (UAV) came into play and the navigation based on computation of the camera path and the distance to obstacles with the aid of the optical flow (OF) became highly demanded. OF is the field of image motion velocities. The success of the OF implementation is based on the accessibility of its calculation with the aid of relatively simple algorithms, like Lucas-Kanade, which admits the simple hardware realization. However, the complete OF is the linear function of linear and angular velocities of the UAV which provide an additional means of the navigation parameters. This approach to the UAV navigation presumes the on-board camera giving the video sequence of the underlying surface images providing the information about the UAV evolutions. Extraction of the navigation parameters is made on the basis of exact formulas for OF which gives the description of the observation process for estimation based on Kalman filtering. Since the number of the estimating parameters (linear and angular velocities) is substantially less than the number of measurements (practically the number of the camera pixels), one can expect the high accuracy of these parameters estimation.

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 Download 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.

Karen Stepanyan, Boris Miller, Aleksandr Miller, Alexey Popov
Development of numerical procedure for control of connected Markov chains Download paper
Abstract: The system of controlled time-inhomogeneous Markov chains (MC) is considered. The principal problem is the ``curse of dimension'' which appears here as the necessity of solving the system of ordinary differential equations of high dimension. Moreover, even the development of the system itself is a serious issue since these equations are linked and the standard parallelization approach developed in existing software packages are not very effective. Meanwhile, one can observe that the minimization procedure needed for the right hand side of this system may be easily parallelized since for each equation the minimization procedure may be realized independently. As an example we consider the management of linked dams under seasonal random inflows/outflows and customers' demands. The current state of each dam is the state of continuous-time Markov chain corresponding to the water level. So the state of the dams system is represented in tensor form. The connection of Markov chains is due to the controlled flow between dams. The aim of the control is to keep balance under the natural perturbation and at the same time to satisfy the customers' demands. The general approach to the solution is based on the dynamic programming method which leads to the solution of Bellman type equation in tensor form. This equation may be reduced to the system of ordinary differential equations. Here we suggested the automatic procedure of this system generation and an approach to the minimization which may be realized for each state independently.

Boris Miller
Alexey Popov, Aleksandr Miller, Boris Miller, Karen Stepanyan
Application of the Optical Flow as a Navigation Means for UAV Download paper
Abstract: Recently, relatively small and even micro unmanned aerial vehicles (UAV) came into play and the navigation based on computation of the camera path and the distance to obstacles with the aid of the optical flow (OF) became highly demanded. OF is the field of image motion velocities. The success of the OF implementation is based on the accessibility of its calculation with the aid of relatively simple algorithms, like Lucas-Kanade, which admits the simple hardware realization. However, the complete OF is the linear function of linear and angular velocities of the UAV which provide an additional means of the navigation parameters. This approach to the UAV navigation presumes the on-board camera giving the video sequence of the underlying surface images providing the information about the UAV evolutions. Extraction of the navigation parameters is made on the basis of exact formulas for OF which gives the description of the observation process for estimation based on Kalman filtering. Since the number of the estimating parameters (linear and angular velocities) is substantially less than the number of measurements (practically the number of the camera pixels), one can expect the high accuracy of these parameters estimation.

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 Download 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.

Karen Stepanyan, Boris Miller, Aleksandr Miller, Alexey Popov
Development of numerical procedure for control of connected Markov chains Download paper
Abstract: The system of controlled time-inhomogeneous Markov chains (MC) is considered. The principal problem is the ``curse of dimension'' which appears here as the necessity of solving the system of ordinary differential equations of high dimension. Moreover, even the development of the system itself is a serious issue since these equations are linked and the standard parallelization approach developed in existing software packages are not very effective. Meanwhile, one can observe that the minimization procedure needed for the right hand side of this system may be easily parallelized since for each equation the minimization procedure may be realized independently. As an example we consider the management of linked dams under seasonal random inflows/outflows and customers' demands. The current state of each dam is the state of continuous-time Markov chain corresponding to the water level. So the state of the dams system is represented in tensor form. The connection of Markov chains is due to the controlled flow between dams. The aim of the control is to keep balance under the natural perturbation and at the same time to satisfy the customers' demands. The general approach to the solution is based on the dynamic programming method which leads to the solution of Bellman type equation in tensor form. This equation may be reduced to the system of ordinary differential equations. Here we suggested the automatic procedure of this system generation and an approach to the minimization which may be realized for each state independently.

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

Leonid Mirny
Ekaterina Khrameeva, Geoffrey Fudenberg, Mikhail Gelfand, Leonid Mirny
History of chromosome rearrangement reflects spatial organization of the yeast chromain Download 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.

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

Elena Stavrovskaya, Alexander Favorov, Sarah Wheelan, Andrew Mironov
StereoGene: a tool for fast genomewide correlation assessment Download 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.

Svetlana Vinogradova, Ruslan Soldatov, Andrew Mironov
RNA probing-directed genome-wide detection of structured RNAs Download paper
Abstract: RNA elements are known to regulate cell processes co- and post-transcriptionally. The functions of many regulatory RNA elements depend on their structure, so it is important to be able to determine the structure as well as to scan genomes for structured elements. Classic approaches to predict structured RNAs rely on DNA sequence analysis. There are two major types of information inferred from the sequence: thermodynamic stability of an RNA structure and evolutionary selection on base pair interactions. Last several years chemical probing of RNA as an alternative source of structural information gains popularity. There exist plenty of methods to integrate probing data into RNA secondary structure prediction algorithms. However, whether probing data could somehow contribute to detection of structured RNAs still remains open question. We previously developed energy-based approach RNASurface to detect locally optimal structured RNA elements. Now we integrate probing data into RNASurface energy model. We show that addition of experimental data allows better discrimination of ncRNAs from other transcripts. Application to genome-wide analysis with PARS data uncovers hundreds of previously undetectable segments, and some of them may be functional.

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

Alexander Favorov, Vasily Ramensky, Andrew Mironov
Genes that are best friends: rank-backwards-rank normalization of correlation matrix Download paper
Abstract: We analyze recently proposed multimedia digital fingerprint- ing codes and derive first results on a new arising combinatorial problem.

Mohamed H. Mostafa
Mohamed H. Mostafa, Martin Bossert
Combinatorial Metrics and Collaborative Error/Erasure Decoding for Translational Metrics Download paper
Abstract: The combinatorial metric is a huge family of metrics. Metrics such as Hamming, burst and array (criss-cross or cover) metrics are special cases of this metric (translational metrics). The decoding problem in such a metric can be simplified by dividing it into smaller decoding problems in Hamming metric (being the widely used metric). This has been already done for both burst and array metrics. A general form of such simplification can be achieved through graph coloring. Although the coloring problem is NP hard, it has to be solved once per metric. For different combinatorial metrics the same coloring can be used if a certain relation is satisfied. A "novel" method of decoding in translational metrics beyond half the minimum distance using error/erasure decoders is introduced. By exploiting the properties of the metrics, we obtain a gain in the decoding radius but introduce decoding failures, however, with negligible probability.

Mikhail Moldovan
Mikhail Moldovan, Svetlana Petrova
Comparative genomics analysis of thiamine-pyrophosphate riboswitches in fungal genomes Download 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.

Pavel Mozgunov
Mark Kelbert, Pavel Mozgunov
Asymptotic analysis of the Renyi, Tsallis and Fisher entropies in a Bayesian problem Download paper
Abstract: Consider a Bayesian problem of estimating of probability of success in a series of trials with binary outcomes. We study the asymptotic behaviour of weighted differential entropy for posterior probability density function (PDF) conditional on x successes after n trials, when n to infinity. Suppose that one is interested to know whether the coin is fair or not and for large n is interested in true frequency. In other words, one wants to emphasize the parameter value p=1/2. To do so the concept of weighted differential entropy introduced in [Belis1968] is used when the frequency gamma is necessary to emphasize. It was found that the weight in suggested form does not change the asymptotic form of Shannon, Renyi, Tsallis and Fisher entropies, but change the constants. The leading term in weighted Fisher Information is changed by some constant which depend on distance between the true frequency and the value we want to emphasize.

Vera Mukhina
Vera Mukhina
The position of the plastid ancestor among cyanobacteria Download 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.


up

N

Dmitry Namiot
Manfred Schneps-Schneppe, Dmitry Namiot
On the Network Proximity in City-Scale Ubiquitous Systems Download 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.

Sergey Naumenko
Sergey Naumenko
Iterative target contig assembler (iTCA) Download 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.

Ksenia Lezhnina, Sergey Naumenko, Georgii Bazykin, Alexey Kondrashov
Permissive synonymous mutations facilitate subsequent nonsynonymous mutations in vertebrate genomes Download 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.

Pavel Nekrasov
Pavel Nekrasov, Denis Fakhriev, Dmitry Doronin
Method for providing QoS for real-time flows in MANET with dynamic TDMA Download paper
Abstract: В работе решается задача обеспечения качества обслуживания потоков реального времени в многошаговой беспроводной самоорганизующейся сети с динамическим TDMA. Задача заключается в разработке метода выбора слотов на маршруте таким образом, чтобы выполнялись ограничения на задержку и вероятность доведения пакета от источника до получателя, и при этом максимизировалась емкость сети, измеряемая в числе одновременно запущенных потоков реального времени с удовлетворительным качеством.

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

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

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

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

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 Download 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.

Dmitry Nikolaev, Elena Limonova, Dmitrii Ilin
Improving neural network performance on SIMD architectures Download paper
Abstract: Данная работа посвящена методам ускорения нейросетевого распознавания образов на SIMD архитектурах на примере ARM NEON. Рассмотрен способ ускорения распознавания образов, доступный для ряда современных процессоров: использование SIMD расширений. Описано использование нейронных сетей в задачах распознавания образов, и выделены наиболее трудоемкие операции. Рассмотрены такие методы ускорения матричных вычислений, как использование типа half float и использование целочисленной арифметики. Показан способ векторизации вычислений нелинейных функций активации в нейронных сетях. Приведены экспериментальные результаты ускорения полносвязных и сверточных нейронных сетей на ARM NEON.

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 Download paper
Abstract: В статье рассматривается влияние применения полихроматического рентгеновского пучка для зондирования в методе рентгеновской томографии на точность реконструкции изображений. Проводится анализ 2-мерного варианта задачи. Для изучения влияния параметров эксперимента на выраженность артефактов численно реализована программа моделирования результатов эксперимента. Предложен критерий численной оценки выраженности артефактов восстановления с точки зрения возможности дальнейшей оценки качества реконструкции. Представлены и обсуждаютсярезультаты применения критерия к модельным расчетам для разных композиций химических элементов.

Alexandr Sheshkus, Dmitry Nikolaev, Anastasiya Ingacheva, Natalya Skoryukina
Approach to the recognition of flexible forms on the example of the credit card date recognition Download paper
Abstract: В данной работе рассматривается задача поиска информационных полей документа с гибкой формой на примере распознавания даты окончания срока действия кредитной карты. Обсуждаются принципиальные трудности этой задачи и предлагаются методы ее решения. Рассматриваемая задача решается для случая применения на мобильных устройствах, что накладывает жесткие требования на вычислительную сложность. В работе приводятся результаты формального анализа производительности и точности предложенного алгоритма. Спектр ошибок системы распознавания как целого показывает, что предложенный алгоритм решает задачу с требуемой точностью.

Victor Prun, Dmitry Nikolaev, Marina Chukalina, Anastasiya Ingacheva, Aleksey Buzmakov
Non-linear Algebraic Reconstruction Technique for Non-Monochromatic Computed Tomography Download paper
Abstract: Рассматривается задача реконструкции компьютерной томографии с существенно немонохроматическим источником излучения. Показывается наличие характерных артефактов, возникающих при использовании обычных монохроматических алгоритмов для восстановления таких синограмм. Предлагается модификация алгебраического метода реконструкции для такого эксперимента. Вместо типично используемых методов борьбы с артефактами в виде регуляризации или фильтрации входных данных, предлагается внести изменения в постановку задачи. Задача восстановления сводится от вычисление функции затухания рентгеновского излучения, к вычислению концентраций заранее ограниченного набора элементов, составляющих исследуемый объект. Для восстановления концентраций предлагается использовать алгебраический метод. Выведен шаг итерации для такой задачи и описан модельный пример.

Egor Ershov, Simon Karpenko, Dmitry Nikolaev, Arseniy Terekhin
About accurate assessment of the inaccuracies of the approximation of straight in the fast Hough transform algorithm Download paper
Abstract: В данной работе проведен анализ точности быстрого преобразования Хафа. В этом алгоритме используются аппроксимация прямых дискретными паттернами специального вида, называемыми диадическими прямыми. Предложен явный способ вычисления координат точек данной прямой, а также проведены теоретические и эмпирические оценки ошибки отклонения диадической от идеальной геометрической прямой.

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

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

Maxim Nuraliev
Mikhail Schelkunov, Maxim Nuraliev, Aleksey Penin, Maria Logacheva
Nuclear genome changes accompanying a loss of photosynthesis in orchids of genus Epipogium Download 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.


up

O

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

Ibrahim Taner Okumus
Diyar Jamal Hamad, Khirota Gorgees Yalda, Ibrahim Taner Okumus
Getting traffic statistics from network devices in an SDN environment using OpenFlow Download paper
Abstract: SDN/OpenFlow network architecture provides a significant advantage over other because it is easier to tune up and introduce new functionalities. Even if many papers focus on the problem of network management, monitoring and control to improve the QoS seen by the customers, only some supply solutions for measuring network performance, e.g., latency, throughput, and packet loss, but our is different by measuring QoS and count byte in each link or port, In terms of network monitoring, OpenFlow allows to build a monitoring solution adjusted to the specific network needs. In this paper, we demonstrate how to use OpenFlow features to get traffic statistics from network devices. In our test environment, collected traffic statistics is used to calculate the available bandwidth on each link in the network. We analyze the effect of statistics collection frequency on the network load and the accuracy of the results collected.

Dmitry Osipov
Dmitry Osipov
Robust order statistics-based receiver: complexity issues and performance evaluation Download 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.

Ilya Osipov
Ilya Osipov
Characterization theorems for class of finite frames of product logic KxK Download paper
Abstract: В работе рассматривается вопрос о характеризации множества формул языка первого порядка, задающих бимодальные свойства моделей, в терминах бисимуляций. При этом рассматриваются классы моделей бимодальной логики K*K -- класс моделей на шкалах-произведениях, класс всех моделей логики K*K и класс моделей с одним отношением и двуместными предикатами. В каждом из случаев оказывается возможным ограничить семантику, рассматривая только конечные модели.


up

P

Alexander Panchin
Alexander Panchin, Yuri Panchin, Alexander Tuzhikov
Clusters of genes with different phylogenetic histories Download paper
Abstract: Different subsets of protein-coding sequences may sometimes yield contradictory phylogenetic trees. These discrepancies may be based on different evolutionary histories of genes from a single genome: some sequences were acquired from a direct ancestor, some resulted from horizontal gene transfer, some could be present in a genome due to contaminations of its assembly. Changes in sequence evolutionary rates may also contribute to these effects. We have developed an automated approach to detect protein-coding sequences with regular and irregular evolutionary histories by comparing arrays of BLAST bit scores and hierarchical clustering of sequences with similar arrays of these scores. Our approach allows the discrimination of sequences from different organism sources in in silico metagenomic experiments. Also is surprisingly reveals the presence of large gene clusters in several sequenced genomes. The biological meaning of the latter finding is discussed.

Yuri Panchin
Alexander Panchin, Yuri Panchin, Alexander Tuzhikov
Clusters of genes with different phylogenetic histories Download paper
Abstract: Different subsets of protein-coding sequences may sometimes yield contradictory phylogenetic trees. These discrepancies may be based on different evolutionary histories of genes from a single genome: some sequences were acquired from a direct ancestor, some resulted from horizontal gene transfer, some could be present in a genome due to contaminations of its assembly. Changes in sequence evolutionary rates may also contribute to these effects. We have developed an automated approach to detect protein-coding sequences with regular and irregular evolutionary histories by comparing arrays of BLAST bit scores and hierarchical clustering of sequences with similar arrays of these scores. Our approach allows the discrimination of sequences from different organism sources in in silico metagenomic experiments. Also is surprisingly reveals the presence of large gene clusters in several sequenced genomes. The biological meaning of the latter finding is discussed.

Victor Kuznetsov, Georgy Slivko-Koltchik, Yuri Panchin
H. megidis - a new model organism for electrophysiological studies of the rhythmic oscillations Download 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.

Georgy Slivko-Koltchik, Victor Kuznetsov, Yuri Panchin
Voltage dependent and intrinsic cellular mechanisms in an ultradian rhythm generator for nematode Download 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.

Maxim Panov
Maxim Panov
About accuracy of Gaussian approximation of posterior distribution in growing dimension models Download paper
Abstract: The aim of the paper is to obtain tight bounds for Gaussian approximation of the marginal posterior distribution in quite general parametric setup. We follow the presentation of (Panov & Spokoiny, 2015) and work essentially under the same conditions. However, we prove that the total variation distance between posterior distribution of target parameter and corresponding Gaussian distribution can be bounded by the error term of the order p , q^{1/2}, n^{1/2}, where p is the dimension of the full parameter, q is the dimension of the target parameter and n is the sample size, which improves the bound p^{3/2} / n^{1/2} known previously. We also establish better contraction rate for the posterior distribution of the target parameter. The results can be directly applied in the sieve approach to the semiparametric inference.

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

Aleksey Penin
Mikhail Schelkunov, Maxim Nuraliev, Aleksey Penin, Maria Logacheva
Nuclear genome changes accompanying a loss of photosynthesis in orchids of genus Epipogium Download 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.

Maria Andrianova, Vladimir Seplyarskiy, Maria Logacheva, Anna Klepikova, Aleksey Penin, Georgii Bazykin, Alexey Kondrashov
Identification de novo mutations in highly polymorphic species Download 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.

Svetlana Petrova
Mikhail Moldovan, Svetlana Petrova
Comparative genomics analysis of thiamine-pyrophosphate riboswitches in fungal genomes Download 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.

Dmitry Petrov
Dmitry Petrov, Yulia Dodonova, Leonid Zhukov
Differences in Structural Connectomes between Typically Developing and Autism Groups Download paper
Abstract: We study differences in structural connectomes between typically developing and autism spectrum disorders individuals with machine learning techniques using connection weights and network metrics as features. We build linear SVM classifier with accuracy score 0.64 and report 16 features (seven connection weights and nine network node centralities) best distinguishing these two groups.

Dmitry Petrov, Yulia Dodonova, Leonid Zhukov
Comparison of the kernel effectiveness of SVM classifier to distinguish gender based on the structural connectome Download paper
Abstract: Мы решаем задачу различения пола на основе структурных коннектом с помощью метода опорных векторов с 16 различными ядрами и тремя нормировками исходных данных. Для каждого из ядер и для каждой из нормировок мы сравниваем точность классификации с помощью площади под ROC-кривой. Лучшие результаты - 0.77, дают гауссово и полиномиальные ядра на графах длин кратчайших путей на бинаризованных исходных данных.

Alexander Podkopaev
Yury Maximov, Alexander Podkopaev
Optimal Protein Packing by Convex Optimization Download 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.

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

Alexey Popov
Alexey Popov, Aleksandr Miller, Boris Miller, Karen Stepanyan
Application of the Optical Flow as a Navigation Means for UAV Download paper
Abstract: Recently, relatively small and even micro unmanned aerial vehicles (UAV) came into play and the navigation based on computation of the camera path and the distance to obstacles with the aid of the optical flow (OF) became highly demanded. OF is the field of image motion velocities. The success of the OF implementation is based on the accessibility of its calculation with the aid of relatively simple algorithms, like Lucas-Kanade, which admits the simple hardware realization. However, the complete OF is the linear function of linear and angular velocities of the UAV which provide an additional means of the navigation parameters. This approach to the UAV navigation presumes the on-board camera giving the video sequence of the underlying surface images providing the information about the UAV evolutions. Extraction of the navigation parameters is made on the basis of exact formulas for OF which gives the description of the observation process for estimation based on Kalman filtering. Since the number of the estimating parameters (linear and angular velocities) is substantially less than the number of measurements (practically the number of the camera pixels), one can expect the high accuracy of these parameters estimation.

Karen Stepanyan, Boris Miller, Aleksandr Miller, Alexey Popov
Development of numerical procedure for control of connected Markov chains Download paper
Abstract: The system of controlled time-inhomogeneous Markov chains (MC) is considered. The principal problem is the ``curse of dimension'' which appears here as the necessity of solving the system of ordinary differential equations of high dimension. Moreover, even the development of the system itself is a serious issue since these equations are linked and the standard parallelization approach developed in existing software packages are not very effective. Meanwhile, one can observe that the minimization procedure needed for the right hand side of this system may be easily parallelized since for each equation the minimization procedure may be realized independently. As an example we consider the management of linked dams under seasonal random inflows/outflows and customers' demands. The current state of each dam is the state of continuous-time Markov chain corresponding to the water level. So the state of the dams system is represented in tensor form. The connection of Markov chains is due to the controlled flow between dams. The aim of the control is to keep balance under the natural perturbation and at the same time to satisfy the customers' demands. The general approach to the solution is based on the dynamic programming method which leads to the solution of Bellman type equation in tensor form. This equation may be reduced to the system of ordinary differential equations. Here we suggested the automatic procedure of this system generation and an approach to the minimization which may be realized for each state independently.

Nadezhda Potapova
Nadezhda Potapova, Maria Andrianova, Georgii Bazykin, Alexey Kondrashov
Accumulation of mutations in nonsense alleles of Drosophila melanogaster Download 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.

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

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

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

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

Victor Prun
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 Download paper
Abstract: В статье рассматривается влияние применения полихроматического рентгеновского пучка для зондирования в методе рентгеновской томографии на точность реконструкции изображений. Проводится анализ 2-мерного варианта задачи. Для изучения влияния параметров эксперимента на выраженность артефактов численно реализована программа моделирования результатов эксперимента. Предложен критерий численной оценки выраженности артефактов восстановления с точки зрения возможности дальнейшей оценки качества реконструкции. Представлены и обсуждаютсярезультаты применения критерия к модельным расчетам для разных композиций химических элементов.

Victor Prun, Dmitry Nikolaev, Marina Chukalina, Anastasiya Ingacheva, Aleksey Buzmakov
Non-linear Algebraic Reconstruction Technique for Non-Monochromatic Computed Tomography Download paper
Abstract: Рассматривается задача реконструкции компьютерной томографии с существенно немонохроматическим источником излучения. Показывается наличие характерных артефактов, возникающих при использовании обычных монохроматических алгоритмов для восстановления таких синограмм. Предлагается модификация алгебраического метода реконструкции для такого эксперимента. Вместо типично используемых методов борьбы с артефактами в виде регуляризации или фильтрации входных данных, предлагается внести изменения в постановку задачи. Задача восстановления сводится от вычисление функции затухания рентгеновского излучения, к вычислению концентраций заранее ограниченного набора элементов, составляющих исследуемый объект. Для восстановления концентраций предлагается использовать алгебраический метод. Выведен шаг итерации для такой задачи и описан модельный пример.


up

R

Vasily Ramensky
Alexander Favorov, Vasily Ramensky, Andrew Mironov
Genes that are best friends: rank-backwards-rank normalization of correlation matrix Download paper
Abstract: We analyze recently proposed multimedia digital fingerprint- ing codes and derive first results on a new arising combinatorial problem.

Daria Reshetova
Daria Reshetova, Yury Maximov
Generalization bound for multiclass classifiers Download paper
Abstract: Рассматривается задача многоклассовой классификации. Для нее приводится верхняя оценка радемахеровской сложности множества многоклассовых классификаторов, основанных на минимизации суммарного отступа объектов, и оценки их обобщающей ошибки. Существенно то, что данные оценки приводятся без дополнительных предположений на распределение данных и множество классификаторов.

Revenko Rina
Revenko Rina
A new post-quantum cryptosystem based on newly discovered decoding algorithm of Reed-Muller codes Download 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.

Dmitry Rodionov
Olga Sigalova, Dmitry Rodionov
Comparative Genomics of Arginine Biosynthesis Pathways and Regulons in Human Microbiome Download 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.

Semen Leyn, Dmitry Rodionov
Genomic reconstruction of histidine metabolism and regulation in human microbiome Download 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.

Matvei Khoroshkin, Dmitry Rodionov
Diverse strategies for transcriptional control of central carbohydrate metabolism in Bacteria Download 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.

Pavel Rybin
Pavel Rybin
The erasure-correcting capabilities of low-complexity decoded H-LDPC code as irregular LDPC code Download 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.


up

S

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

Mikhail Schelkunov
Mikhail Schelkunov, Maxim Nuraliev, Aleksey Penin, Maria Logacheva
Nuclear genome changes accompanying a loss of photosynthesis in orchids of genus Epipogium Download 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.

Manfred Schneps-Schneppe
Manfred Schneps-Schneppe, Dmitry Namiot
On the Network Proximity in City-Scale Ubiquitous Systems Download 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.

Viktor Selionov
Dmitry Zhvansky, Viktor Selionov, Irina Solopova
Interlimb interactions in health and in Parkinson's disease Download paper
Abstract: В условиях горизонтальной вывески верхних и нижних конечностей изучали влияние движений рук и движений в отдельных их суставах на электрофизиологические и кинематические характеристики произвольных и вызванных вибрацией шагоподобных движений ног у здоровых испытуемых и у пациентов с болезнью Паркинсона (БП). У здоровых испытуемых движения рук приводили к потенциации двигательной активности ног. Межсегментарные взаимодействия во время совместных движений рук и ног у больных были существенно ослаблены, вероятно, вследствие искажения центральных моторных команд.

Alexander Seliverstov
Semen Korolev, Oleg Zverkov, Sergei Lyzhin, Alexander Seliverstov, Vassily Lyubetsky
A Search for Genes Encoding Histidine-Containing Leader Peptides in Actinobacteria Download 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.

Roman Gershgorin, Konstantin Gorbunov, Alexander Seliverstov, Vassily Lyubetsky
Evolution of Chromosome Structures Download 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.

Vladimir Seplyarskiy
Vladimir Seplyarskiy, Georgii Bazykin
APOBEC induced mutations are strongly enriched in DNA regions replicating as the lagging strand Download paper
Abstract: APOBEC3B, a cytidine deaminase of the APOBEC family, is one of the main factors causing mutations in human cancers1-4. APOBEC3B specifically deaminates cytosines on single stranded DNA (ssDNA)3,5-8. A fraction of the APOBEC3B-induced mutations occur as clusters ('kataegis') in ssDNA produced during reparation of double-stranded breaks (DSBs). However, the properties of the remaining 87% of APOBEC3B induced mutations, specifically, the source of the ssDNA and the genomic distribution, are largely unknown1,3. Our analysis of genomic1,9 and exomic (TCGA) cancer databases demonstrates that the DNA regions which are usually lagging during DNA replication, and therefore temporarily exist as ssDNA10-12, are the major target of APOBEC3B, carrying >33% of dispersed APOBEC3B-induced mutations. Unexpectedly, while methylated cytosine is generally more mutation-prone than non-methylated cytosine, we report that methylation reduces the rate of APOBEC3B-induced mutations by a factor of ~2. Lastly, we show that in cancers with intensive APOBEC3B-induced mutagenesis, there is almost no increase in mutation rates in late replicating regions (contrary to other cancers); as late-replicating regions are depleted in exons, this results in a 1.3-fold higher fraction of mutations falling into exons. This study provides novel insights into the APOBEC3B-induced mutagenesis, and suggests that mutational processes are severely perturbed in genomes of cancers with the APOBEC3B signature.

Maria Andrianova, Vladimir Seplyarskiy, Maria Logacheva, Anna Klepikova, Aleksey Penin, Georgii Bazykin, Alexey Kondrashov
Identification de novo mutations in highly polymorphic species Download 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.

Nadezhda Terekhanova, Georgii Bazykin, Ruslan Soldatov, Vladimir Seplyarskiy
Evolution of local mutation rate and its determinants Download paper
Abstract: Knowledge of mutation rate heterogeneity within the human genome is very applicable in genome-wide association studies. Mutation rate variation is known to be associated with the changes of DNA features; however the main portion of it remains unexplained. Here we show that the correlation between human and chimp 1 Mb regions ~95% and becomes ~30 % lower when we compare human mutation rate with mutation rate in the Strepsirrhini clade. Recombination rate and in a lesser extent replication timing and DNase-hypersensitive sites possess the excess of explained variance for mutation rate in regions in which it changed recently. Although, landscapes of genomic features accumulate fewer changes compared with the landscape of the mutation rate, we found that shifts in distributions of genomic features correlate significantly with the changes in the local mutation rate between species in 1 Mb windows. These findings should be taken into account while constructing evolutionary models.

Yana Shabelnikova
Yana Shabelnikova, Eugene Yakimov
Combined use of EBIC and XBIC methods for determination of diffusion length and recombination activity of grain boundaries in silicon Download paper
Abstract: В работе описан подход к определению диффузионной длины неосновных носителей заряда L и скорости рекомбинации на границе зерна Vs в кремнии посредством одновременного использования результатов EBIC и XBIC измерений. Показано, что невязка между экспериментально измеренным и модельным профилями контраста наведенного тока для обоих методов чувствительна к изменению только одного из пары параметров L и Vs. Поэтому искомые величины определяются как значения, при которых минимума достигает полусумма невязок для EBIC и XBIC методов.

Lyubov Shatalova
Dmitrii Borisevich, Lyubov Shatalova, Valery Ilinsky
Refining mutations considered pathogenic using benign variants features Download 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.

Pavel Shelyakin
Anna Kaznadzey, Pavel Shelyakin
Co-evolution of carbohydrate metabolism genes of same and different functional classes in bacteria Download 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.

Pavel Shelyakin
Prediction of transcriptional regulation by sigma factors in bacterial genomes with known TSS Download 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.

Alexandr Sheshkus
Alexandr Sheshkus, Dmitry Nikolaev, Anastasiya Ingacheva, Natalya Skoryukina
Approach to the recognition of flexible forms on the example of the credit card date recognition Download paper
Abstract: В данной работе рассматривается задача поиска информационных полей документа с гибкой формой на примере распознавания даты окончания срока действия кредитной карты. Обсуждаются принципиальные трудности этой задачи и предлагаются методы ее решения. Рассматриваемая задача решается для случая применения на мобильных устройствах, что накладывает жесткие требования на вычислительную сложность. В работе приводятся результаты формального анализа производительности и точности предложенного алгоритма. Спектр ошибок системы распознавания как целого показывает, что предложенный алгоритм решает задачу с требуемой точностью.

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

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

Olga Sigalova
Olga Sigalova, Dmitry Rodionov
Comparative Genomics of Arginine Biosynthesis Pathways and Regulons in Human Microbiome Download 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.

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

Natalya Skoryukina
Alexandr Sheshkus, Dmitry Nikolaev, Anastasiya Ingacheva, Natalya Skoryukina
Approach to the recognition of flexible forms on the example of the credit card date recognition Download paper
Abstract: В данной работе рассматривается задача поиска информационных полей документа с гибкой формой на примере распознавания даты окончания срока действия кредитной карты. Обсуждаются принципиальные трудности этой задачи и предлагаются методы ее решения. Рассматриваемая задача решается для случая применения на мобильных устройствах, что накладывает жесткие требования на вычислительную сложность. В работе приводятся результаты формального анализа производительности и точности предложенного алгоритма. Спектр ошибок системы распознавания как целого показывает, что предложенный алгоритм решает задачу с требуемой точностью.

Georgy Slivko-Koltchik
Victor Kuznetsov, Georgy Slivko-Koltchik, Yuri Panchin
H. megidis - a new model organism for electrophysiological studies of the rhythmic oscillations Download 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.

Georgy Slivko-Koltchik, Victor Kuznetsov, Yuri Panchin
Voltage dependent and intrinsic cellular mechanisms in an ultradian rhythm generator for nematode Download 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.

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

Nadezhda Terekhanova, Georgii Bazykin, Ruslan Soldatov, Vladimir Seplyarskiy
Evolution of local mutation rate and its determinants Download paper
Abstract: Knowledge of mutation rate heterogeneity within the human genome is very applicable in genome-wide association studies. Mutation rate variation is known to be associated with the changes of DNA features; however the main portion of it remains unexplained. Here we show that the correlation between human and chimp 1 Mb regions ~95% and becomes ~30 % lower when we compare human mutation rate with mutation rate in the Strepsirrhini clade. Recombination rate and in a lesser extent replication timing and DNase-hypersensitive sites possess the excess of explained variance for mutation rate in regions in which it changed recently. Although, landscapes of genomic features accumulate fewer changes compared with the landscape of the mutation rate, we found that shifts in distributions of genomic features correlate significantly with the changes in the local mutation rate between species in 1 Mb windows. These findings should be taken into account while constructing evolutionary models.

Svetlana Vinogradova, Ruslan Soldatov, Andrew Mironov
RNA probing-directed genome-wide detection of structured RNAs Download paper
Abstract: RNA elements are known to regulate cell processes co- and post-transcriptionally. The functions of many regulatory RNA elements depend on their structure, so it is important to be able to determine the structure as well as to scan genomes for structured elements. Classic approaches to predict structured RNAs rely on DNA sequence analysis. There are two major types of information inferred from the sequence: thermodynamic stability of an RNA structure and evolutionary selection on base pair interactions. Last several years chemical probing of RNA as an alternative source of structural information gains popularity. There exist plenty of methods to integrate probing data into RNA secondary structure prediction algorithms. However, whether probing data could somehow contribute to detection of structured RNAs still remains open question. We previously developed energy-based approach RNASurface to detect locally optimal structured RNA elements. Now we integrate probing data into RNASurface energy model. We show that addition of experimental data allows better discrimination of ncRNAs from other transcripts. Application to genome-wide analysis with PARS data uncovers hundreds of previously undetectable segments, and some of them may be functional.

Ruslan Soldatov
Patterns of microRNA biogenesis and expression in the process of Unfolded Protein Response Download 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.

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

Irina Solopova
Dmitry Zhvansky, Viktor Selionov, Irina Solopova
Interlimb interactions in health and in Parkinson's disease Download paper
Abstract: В условиях горизонтальной вывески верхних и нижних конечностей изучали влияние движений рук и движений в отдельных их суставах на электрофизиологические и кинематические характеристики произвольных и вызванных вибрацией шагоподобных движений ног у здоровых испытуемых и у пациентов с болезнью Паркинсона (БП). У здоровых испытуемых движения рук приводили к потенциации двигательной активности ног. Межсегментарные взаимодействия во время совместных движений рук и ног у больных были существенно ослаблены, вероятно, вследствие искажения центральных моторных команд.

Vladimir Spokoiny
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 Download 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

Sergey Dovgal, Vladimir Spokoiny
Fisher and Wilks Theorems for Likelihood-Based Density Estimation Download paper
Abstract: This paper revisits the local likelihood density estimation approach, introduced by Loader. This method also allows to estimate the derivatives of the density function, and aggregates them in a complex manner to obtain the final estimate. We study properties of the estimate and prove Fisher and Wilks phenomena. The framework of Spokoiny was used to obtain finite-sample bounds for the estimate. We also allow model misspecification and express the error in terms of «model bias».

Kirill Efimov, Vladimir Spokoiny
Smallest accepted method for model selection Download paper
Abstract: This paper presents a method of model selection based on a smallest accepted (SmA) rule: a model is accepted if it is not rejected against any larger model. The final choice is the simplest accepted model. Model comparison is being done by multiple testing. We present oracle results on subset and parameter estimation for the proposed method.

Nazar Buzun, Alexandra Suvorikova, Vladimir Spokoiny
Multiscale parametric approach for change point detection Download paper
Abstract: This work presents a novel algorithm for change point detection, that can be applied for analysis of data of unknown nature. It is based on likelihood-ratio test statistics, as its behaviour can be described in terms of \chi^2-distribution even in case of model misspecification. To discover change point in the quickest way, statistics is calculated in a set of running windows of different scales. Algorithm is self-tuned: critical values are justified by data and calculated with multiplier bootstrap procedure. To make the method more robust for outliers, the concept of change-point patterns is presented.

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

Elena Stavrovskaya, Alexander Favorov, Sarah Wheelan, Andrew Mironov
StereoGene: a tool for fast genomewide correlation assessment Download 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.

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

Ivan Stelmakh
Vladimir V'yugin, Ivan Stelmakh
Generalization of some machine learning algorithms in case of unlimited one-step losses Download paper
Abstract: Рассматриваются модификации алгоритма экспоненциального взвешивания экспертных стратегий и алгоритма Hedge оптимального распределения потерь в режиме онлайн для случая неограниченных одношаговых потерь. Получены оценки ошибки обучения (регрета) этих алгоритмов в случае неограниченных потерь.

Vita Stepanova
Vita Stepanova, Iakov Davydov, Alex Tonevitsky
Regulation of relative abundance of ribosomal proteins L12 and L10 Download 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.

Karen Stepanyan
Alexey Popov, Aleksandr Miller, Boris Miller, Karen Stepanyan
Application of the Optical Flow as a Navigation Means for UAV Download paper
Abstract: Recently, relatively small and even micro unmanned aerial vehicles (UAV) came into play and the navigation based on computation of the camera path and the distance to obstacles with the aid of the optical flow (OF) became highly demanded. OF is the field of image motion velocities. The success of the OF implementation is based on the accessibility of its calculation with the aid of relatively simple algorithms, like Lucas-Kanade, which admits the simple hardware realization. However, the complete OF is the linear function of linear and angular velocities of the UAV which provide an additional means of the navigation parameters. This approach to the UAV navigation presumes the on-board camera giving the video sequence of the underlying surface images providing the information about the UAV evolutions. Extraction of the navigation parameters is made on the basis of exact formulas for OF which gives the description of the observation process for estimation based on Kalman filtering. Since the number of the estimating parameters (linear and angular velocities) is substantially less than the number of measurements (practically the number of the camera pixels), one can expect the high accuracy of these parameters estimation.

Karen Stepanyan, Boris Miller, Aleksandr Miller, Alexey Popov
Development of numerical procedure for control of connected Markov chains Download paper
Abstract: The system of controlled time-inhomogeneous Markov chains (MC) is considered. The principal problem is the ``curse of dimension'' which appears here as the necessity of solving the system of ordinary differential equations of high dimension. Moreover, even the development of the system itself is a serious issue since these equations are linked and the standard parallelization approach developed in existing software packages are not very effective. Meanwhile, one can observe that the minimization procedure needed for the right hand side of this system may be easily parallelized since for each equation the minimization procedure may be realized independently. As an example we consider the management of linked dams under seasonal random inflows/outflows and customers' demands. The current state of each dam is the state of continuous-time Markov chain corresponding to the water level. So the state of the dams system is represented in tensor form. The connection of Markov chains is due to the controlled flow between dams. The aim of the control is to keep balance under the natural perturbation and at the same time to satisfy the customers' demands. The general approach to the solution is based on the dynamic programming method which leads to the solution of Bellman type equation in tensor form. This equation may be reduced to the system of ordinary differential equations. Here we suggested the automatic procedure of this system generation and an approach to the minimization which may be realized for each state independently.

Grigory Sterling
Grigory Sterling, Pavel Prikhodko
Local correlation as a measure of dependence between random variables Download paper
Abstract: В работе ра&#