Abstract:

Abstract: В докладе будет рассказано несколько новых обобщений «теоремы о бутерброде». Говоря элементарным языком, нас будет интересовать, например, такой вопрос: когда от бутерброда с 4-мя ингредиентами можно отрезать меньший бутерброд с теми же вкусовыми качествами. Другой связанный с этим вопрос: когда из бутерброда с 4-мя ингредиентами можно вырезать выпуклый «подбутерброд» заданного размера, на вкус не отличимый от большого. Аналогичные задачи будут обсуждаться во всех размерностях и с разным числом ингредиентов.

Abstract: Рассматривается задача стабилизации движения БПЛА вдоль заданной траектории при наличии внешних аэродинамических возмущений. Опорная траектория задана как набор по-координатных полиномов, полученных в результате решения задачи планирования движения. Задача стабилизации движения сводится к задаче синтеза компенсатора обратной связи по доступным наблюдениям. Рассматриваются два типа возмущений: зона турбулентности и область ветрового сдвига. Начало и окончание зоны ветрового сдвига описываются марковской цепью в непрерывном времени, а направление и интенсивность сдвига как гауссовские случайные векторы.

Abstract: Рассматривается задача разработки интерфейса между физическим и системным уровнями (Link-to-System Mapping Interface или PHY abstraction) для восходящего канала системы LTE-A Release 10. Интерфейс между физическим и системным уровнями является математической моделью, используемой в инструментах имитационного моделирования системного или сетевого уровней для точного определения вероятности пакетной ошибки при заданных условиях распространения сигнала, не требуя полного прямого моделирования процесса передачи пакетов. Для разработки рассматриваемого интерфейса выбран подход, основанный на использовании средней взаимной информации на бит между кодированными битами на передатчике и логарифмами отношения правдоподобия на приемнике. В работе представлены принципы построения интерфейса между физическим и системным уровнями для рассматриваемой системы и полная структура разработанной модели. Приведены результаты верификации интерфейса, показывающие высокую точность определения значения вероятности пакетной ошибки.

Abstract: В рамках проекта создания лаборатории эволюционной геномики на ФББ МГУ возникла подзадача построения вычислительной системы, которую можно использовать для обработки данных, поступающих с высокопроизводительного секвенатора Illumina Hiseq 2000. Созданный центр обработки данных состоит из 30 вычислительных узлов общего назначения, одного узла с большим объемом оперативной памяти (512Gb), трех систем хранения данных по 144TB каждая, сетей обмена данными, вычислительной и служебной сети, графического ускорителя вычислений, кондиционеров и источника бесперебойного питания.

Abstract: CRISPR is a prokaryotic adaptive defence system that provides resistance against alien replicons like viruses and plasmids. Cas-proteins and CRISPRcassettes comprise the entire CRISPR-system. The CRISPR-cassettes include leader sequence at 5' and an array of conserved short direct repeats with unique spacer sequences located between them. The insertion of new spacers predominantly occurs near the leader sequence. Therefore CRISPR-cassettes can be treated as a footprint of phage-bacteria interactions within the certain ecosystem. The human gut is a rich habitat populated by a vast number of microorganisms, however the large proportion of them are referred to the uncultured category and little is known about their CRISPR-systems. We used human gut metagenomic data of three distinct projects to obtain information about the composition and dynamics of CRISPR-cassettes in the humanassociated microbiota. This study shows that CRISPR-cassettes are highly variable and particular CRISPRome of a certain individual reflects it's unique viriome diversity, abundance and dynamics.

Abstract: Бактериальный рибосомный белок L12 является единственным многокопийным белком рибосомы. Рибосома Escherichia coli содержит четыре молекулы белка L12, в то время, как у термофильных бактерий Thermotoga maritima и Thermus thermophilus одна рибосома содержит шесть молекул белка L12. В данной работе мы предсказали число молекул белка L12 в рибосоме более чем для 1200 видов бактерий. Были обнаружены виды, в рибосомах которых присутствуют восемь молекул белка L12. Был проведен филогенетических профилей, коррелирующих с копийностью L12. Рассмотрены возможные механизмы поддержания необходимого соотношения белков в рибосоме.

Abstract: In the current work we explored a possible role of histone modifications in the regulation of alternative polyadenylation. We observed correlations between the usage of a polyadenylation site and the level of certain histone modifications near this site. In order to check if this association can be explained by epigenetic regulation of polymerase II elongation rate, we compared the correlations in the regions of high and low polymerase II occupancy.

Abstract: With the cost of the genome sequencing going down, the need for the effective tools for the analysis of NGS data is becoming urgent. Here, we present a exible Java framework that provides various functionalities for the analysis of mutation data. It operates on various levels of biological objects, such as mutations, genes, pathways etc. and allows for incorporation of other types of data (e.g. gene expression) into analysis. We also provide an example of a framework application to a study of mutations in uencing the expression level of the closely positioned genes.

Abstract: G. aculeatus is a good model for studying population genomics. It exists in two morphs, freshwater and marine, that differ in their morphological, physiological and behavioral traits, and these traits have evolved repeatedly in freshwater populations from marine ancestors all over the world. We use next-generation sequencing to study the genetic variation of the natural marine and freshwater stickleback populations, and of experimental freshwater populations formed ~30 years ago from crosses of marine and freshwater ancestors. We confirm the previously identified QTLs responsible for stickleback phenotypic variation, and find new QTLs. Furthermore, our results show that in the experimental freshwater populations, strong selection favoring the freshwater alleles in these QTLs acted over the time of the experiment. Over these 30 years, selection increased the mean frequency of the freshwater alleles in multiple loci from 50% to 70-80%. It was prominent when the founder population was relatively large, and consisted of 20 individuals; by contrast, drift prevailed in the experimental population founded by a cross of only two individuals.

Abstract: Functional significance of non-coding sequences is commonly assessed through above-random conservation between genomes. However there is accumulating data that points to the rapid turnover of regulatory sequences. In the case of generality of this phenomenon direct similarity-based approaches would be insufficient to infer functional significance of noncoding sequences. Here we address the question of whether functional conservation is possible without sequence conservation. We apply bioinformatics approach to this problem by tracing patterns of conservation in orthologous introns in two distant pair of species. Our findings suggest that orthologous non-coding genomic compartments may continue to play a functional role in distant species even after having diverged beyond recognition at the sequence level.

Abstract: Геномы высших эукариот содержат десятки тысяч сайтов сплайсинга, многие из которых содержат неконсенсусные нуклеотиды. Известно также, что сайты альтернативно сплайсируемых (кассетных) экзонов чаще содержут неконсенсусные нуклеотиды по сравнению с сайтами конститутивных экзонов. В работе обсуждаются эволюционные сценарии, которые могли бы объяснить наблюдаемые отличия между сайтами кассетных и конститутивных экзонов; делается попытка выделить наиболее вероятные из них.

Abstract: Most models of sequence evolution assume independence of mutations at different sites; however, there are multiple possible reasons for deviations from independence. In particular, epistatic interactions between sites may lead to non-independence of SNPs and of nucleotide replacements at distinct sites. Here, we show that epistatic interactions between nearby (at distances of up to 5 bp) nucleotide sites shape the patterns of polymorphism and divergence in coding (CDS) and noncoding (NDS) DNA sequences of D. melanogaster. Both in within-species polymorphism and in interspecies divergence, the clustering of SNPs and substitutions at nearby sites is positively correlated with the degree of conservatism of the sequence segment. Moreover, clustering of substitutions in the same of the two evolving lineages, suggestive of positive selection or epistatic interactions (Bazykin et al. Nature 2004 Jun 3; 429:558-562), is twice as strong in the conserved regions of NDS, and 3 times as strong in the conserved regions of CDS, compared to the corresponding non-conserved regions. These results show that epistatic interactions between nearby CDS and NDS sites are prevalent genome-wise, and may be an underappreciated contributor to sequence evolution.

Abstract:

Abstract: In this article we study simulation-based optimization algorithms for continuous time optimal stopping problems. We derive the convergence rates and discuss some implications of these rates for the choice of the number of Monte-Carlo paths in the optimization step.

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

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

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

Abstract: Dimension reduction in general and manifold learning in particular could be extremely helpful in some practical data mining problems with high dimensionality involved. In this paper several widespread approaches (Isomap, LLE, LTSA, etc.) along with newly proposed GSE algorithm are compared. The quality is measured in terms of test sample reconstruction error. The results showed that GSE outperforms other techniques in terms of reconstruction quality and robustness.

Abstract: В данной работе изучается устойчивость метода решения задачи линейной регрессии с помощью быстрого преобразования Хафа при наличии нормально распределенного аддитивного координатного и выбросового шумов, а также производится сравнение предлагаемого метода с некоторыми робастными модификациями метода наименьших квадратов (МНК) и методами Тейла и Сена. Демонстрируется, что предлагаемый метод является устойчивым, и при наличии сильного выбросового шума дает более точные результаты, нежели варианты метода наименьших квадратов с итеративным пересчетом весов и методы Тейла и Сена. Также показано, что метод БПХ наиболее устойчив в случае, когда дополнительно присутствует некоррелированный шум с круговым нормальным распределением.

Abstract: Рассматриваются изомонодромные деформации систем линейных дифференциальных уравнений с иррегулярными особенностями. Доказывается существование таких деформаций нешлезенгеровского вида.

Abstract: В работе была исследована группа Escherichia coli / Shigella, содержащая более 30 полностью отсеквенированных и аннотированных геномов. На основе данных об ортологических рядах был проанализирован порядок генов и выделены синтенные блоки (участки с совпадающим порядком генов). С помощью алгоритма MGRA было построено эволюционное дерево, реконструирован порядок генов у предков во всех его узлах и перестройки блоков на всех его ветвях. Консервативность порядка универсальных генов в геномах Escherichia coli позволила выделить референсную последовательность универсальных генов (генов, присутствующих во всех рассматриваемых организмах). На основе сопоставления локализации генов и деревьев их аминокислотных последовательностей были выделены гены, перенесенные горизонтально.

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

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

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

Abstract: Статья посвящена ведущейся в нашей лаборатории работе по построению большой онтологии общего назначения. Создаваемый ресурс предназначен для задач семантического анализа текста на любом естественном языке и специально адаптируется для этого. Единицы онтологии соотнесены со словарями системы ЭТАП-3 и словарем искусственного языка-посредника UNL.

Abstract: Актинобактерии — это большая группа семейств, родов и видов, распространённых во многих средах обитания: встречаются преимущественно в почве, а также и в морских осадках, выступают в качестве симбионтов и паразитов. Виды рода Streptomyces — Грам-положительные нитчатые бактерии, которые производят множество вторичных метаболитов, в том числе антибиотиков. Эти бактерии продуцируют более двух третей всех клинически важных антибиотиков и потому вызывают высокий фармакологический и индустриальный интерес. Филогенетический анализ двух штаммов из рода Streptomyces, выделенных из разных губок, показал их близость (99,9% идентичности генов 16S рРНК). Секвенирование, аннотация и анализ геномов этих штаммов Streptomyces показали, что у них был общий почвенный предок с Streptomyces albus. Несмотря на высокое сходство генов «домашнего хозяйства» в изучаемых штаммах и S.albus, некоторые гены биосинтеза вторичного метаболизма могут сохраняться в одном и отсутствовать в другом штамме, подтверждая гипотезу о различных путях эволюции этих Streptomyces. Наши исследования проясняют эволюцию изучаемых стрептомицет в том числе при переходе от почвенного образа жизни к морскому.

Abstract: Рассмотрен прибор для диагностики нарушения цветоощущений. Описаны особенности человеческого цветного зрения. Раскрыты методы быстрого обнаружения патологий, связанных с различением цветов.

Abstract: Problem of aircraft structural components (wing, fuselage, tail) optimization is considered. Solution of this problem is very computationally intensive, since it requires at each iteration a two-level process: first from previous iteration, an update step at full component level must be performed in order to take into account internal loads and their sensitivities in the whole structure involved by changes in local geometry. Second, numerous local analyzes are run on isolated elements (for example, super stiffeners) of structural components in order to calculate mechanical strength criteria and their sensitivities, depending on current internal loads. An optimization step is then performed from combined global-local sensitivities. This bi-level global-local optimization process is then repeated until convergence of load distribution in the whole structure. Numerous calculations of mechanical strength criteria are necessary for local analyzes, resulting in great increase of the time between two iterations. In this work an effective method for speeding up the optimization process was proposed. The method uses surrogate models of optimization constraints (mechanical strength criteria) and provides a reduction of structure optimization computational time from several days to a few hours.

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

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

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

Abstract: Dimension reduction in general and manifold learning in particular could be extremely helpful in some practical data mining problems with high dimensionality involved. In this paper several widespread approaches (Isomap, LLE, LTSA, etc.) along with newly proposed GSE algorithm are compared. The quality is measured in terms of test sample reconstruction error. The results showed that GSE outperforms other techniques in terms of reconstruction quality and robustness.

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

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

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

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

Abstract: В статье предложена новая быстрая версия алгоритма реконструкции компьютерной томографии SART. Итерация алгоритма была асимптотически ускорена с помощью быстрого преобразования Хафа с O(n^3) до O(n^{2}logn). Данный алгоритм был программно реализован на языке С++ и проведен модельный эксперимент, который демонстрирует работу алгоритма.

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

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

Abstract: В статье предложена новая быстрая версия алгоритма реконструкции компьютерной томографии SART. Итерация алгоритма была асимптотически ускорена с помощью быстрого преобразования Хафа с O(n^3) до O(n^{2}logn). Данный алгоритм был программно реализован на языке С++ и проведен модельный эксперимент, который демонстрирует работу алгоритма.

Abstract: Biological nitrogen fixation performed by a variety of bacteria is an important issue for ecology and agriculture. Many legumes require nitrogen-fixing endosymbionts for effective growth. However, little is known about transcriptional organization of such bacteria. We have applied signal-detection techniques to dRNA- sequencing data to create genome-wide map of transcription start sites (TSS) of the model organism Bradyrhizobium japonicum USDA110, soybean symbiont. RNA was extracted from free-living bacteria (FR) and plant root nodule bacteroids (NO), where symbiotic nitrogen fixation occurs, thus making possible determination of differentially expressed loci. The data obtained was used to determine cis-regulatory elements like promoter sequences and transcription factor binding sites involved in gene expression alteration in free-living and symbiotic states.

Abstract: Проблема клинических и субклинических проявлений церебральной сосудистой патологии у детей и их лечение становятся одной из ключевых в детской неврологии. Поэтому развитие детской ангионеврологии в настоящее время невозможно без использования такого метода как ультразвуковая допплерография, объективно отражающая состояние кровоснабжения головного мозга. Разработанный в ИППИ РАН вместе с экспертами метод структурной организации слабоформализованной информации и профессиональных знаний приводит к сокращению их объема и повышению информативности. Комплексный анализ позволил провести сравнительную оценку функционального состояния мозга детей в возрасте от 3 до 8 лет в норме и с нарушениями умственного и речевог&#