检索结果-内蒙古大学图书馆

2016 German Conference on Bioinformatics, GCB 2016

作者： Amirabad, Azim Dehghani Schulz, Marcel H. Cluster of Excellence for Multimodal Computing and Interaction Saarland University Saarbrücken Germany Max Planck Institute for Informatics Saarbrücken Germany International Max Planck Research School for Computer Science Saarbrücken Germany

Deregulation of miRNAs is implicated in many diseases in particular cancer, where miRNAs can act as tumour suppressors or oncogenes. As sequence-based miRNA target predictions do not provide condition-specific information, many algorithms combine expression data for miRNAs and genes for prioritization of miRNA targets. However, common strategies prioritize miRNA-gene associations, although a miRNA may only target a subset of the alternative transcripts produced by a gene. Thus, current approaches are suboptimal. Here we address the problem of transcript and not gene based miRNA target prioritization. We show how to leverage methods that were developed for gene expression based miRNA-target prioritization for transcripts. In addition, we introduce a new multitasking based learning (MTL) method that uses structured-sparsity inducing regularization to improve accuracy of the learning. The new MTL approach performs especially favorable in small sample size settings, for genes with many transcripts and with noisy transcript expression level estimates as shown with simulated data. In an analysis of real liver cancer RNA-seq data we show that the MTL approach better predicts transcript expression and outperforms simpler approaches for miRNA-target prediction. © GCB *** rights reserved.

关键词： RNA

来源：评论

学校读者我要写书评

暂无评论

Gossip vs. Markov chains, and randomness-efficient rumor spreading 26

Gossip vs. Markov chains, and randomness-efficient rumor spr...

引用

26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015

作者： Guo, Zeyu Sunt, He California Institute of Technology Pasadena United States Max Planck Institute for Informatics Saarbriicken Germany Cluster of Excellence Multimodal Computing and Interaction Universitat des Saarlandes Saarbru7dieken Germany

ISBN: (纸本)9781611973747

We study gossip algorithms for the rumor spreading problem which asks one node to deliver a rumor to all nodes in an unknown network, and every node is only allowed to call one neighbor in each round. In this work we introduce two fundamentally new techniques in studying the rumor spreading problem: First, we establish a new connection between the rumor spreading process in an arbitrary graph and certain Markov chains. While most previous work analyzed the rumor spreading time in general graphs by studying the rate of the number of (un-)informed nodes after every round, we show that the mixing time of a certain Markov chain suffices to bound the rumor spreading time in an arbitrary graph. Second, we construct a reduction from rumor spreading processes to branching programs. This reduction gives us a general framework to derandomize the rumor spreading and other gossip processes. In particular, we show that, for any n-vertex expander graph, there is a protocol which informs every node in O(log n) rounds with high probability, and uses O(log n · log log n) random bits in total. The runtime of our protocol is tight, and the randomness requirement of O(log n · log log n) random bits almost matches the lower bound of ω(log n) random bits. We further show that, for many graph families (defined with respect to the expansion and the degree), O(polylog n) random bits in total suffice for fast rumor spreading. These results give us an almost complete understanding of the role of randomness in the rumor spreading process, which was extensively studied over the past years. Copyright © 2015 by the Society for Industrial and Applied Mathmatics.

关键词： Markov processes

来源：评论

学校读者我要写书评

暂无评论

Incremental semantic role labeling with tree adjoining grammar

Incremental semantic role labeling with tree adjoining gramm...

引用

2014 Conference on Empirical Methods in Natural Language Processing, EMNLP 2014

作者： Konstas, Ioannis Keller, Frank Demberg, Vera Lapata, Mirella Institute for Language Cognition and Computation School of Informatics University of Edinburgh United Kingdom Cluster of Excellence Multimodal Computing and Interaction Saarland University Germany

ISBN: (纸本)9781937284961

We introduce the task of incremental semantic role labeling (iSRL), in which semantic roles are assigned to incomplete input (sentence prefixes). iSRL is the semantic equivalent of incremental parsing, and is useful for language modeling, sentence completion, machine translation, and psycholinguistic modeling. We propose an iSRL system that combines an incremental TAG parser with a semantically enriched lexicon, a role propagation algorithm, and a cascade of classifiers. Our approach achieves an SRL Fscore of 78.38% on the standard CoNLL 2009 dataset. It substantially outperforms a strong baseline that combines gold-standard syntactic dependencies with heuristic role assignment, as well as a baseline based on Nivre's incremental dependency parser. © 2014 Association for Computational Linguistics.

关键词： Semantics

来源：评论

学校读者我要写书评

暂无评论

Parameterized Algorithmics for Computational Social Choice:Nine Research Challenges

引用

Tsinghua Science and Technology 2014年第4期19卷 358-373页

作者： Robert Bredereck Jiehua Chen Piotr Faliszewski Jiong Guo Rolf Niedermeier Gerhard J.Woeginger the Institut fr Softwaretechnik und Theoretische Informatik TU Berlin Berlin Germany AGH University of Science and Technology Kraków Poland the Cluster of Excellence Multimodal Computing and Interaction Universitt des SaarlandesSaarbrcken Germany the Department of Mathematics and Computer Science TU Eindhoven Eindhoven The Netherlands

Computational Social Choice is an interdisciplinary research area involving Economics, Political Science,and Social Science on the one side, and Mathematics and Computer Science（including Artificial Intelligence and Multiagent Systems） on the other side. Typical computational problems studied in this field include the vulnerability of voting procedures against attacks, or preference aggregation in multi-agent systems. Parameterized Algorithmics is a subfield of Theoretical Computer Science seeking to exploit meaningful problem-specific parameters in order to identify tractable special cases of in general computationally hard problems. In this paper, we propose nine of our favorite research challenges concerning the parameterized complexity of problems appearing in this context. This work is dedicated to Jianer Chen, one of the strongest problem solvers in the history of parameterized algorithmics,on the occasion of his 60 th birthday.

关键词： NP-hard problems parameterized complexity fixed-parameter tractability kernelization exact algorithms voting decision making cake cutting

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity of local search for TSP, more refined

The parameterized complexity of local search for TSP, more r...

引用

作者： Guo, Jiong Hartung, Sepp Niedermeier, Rolf Suchý, Ondřej Cluster of Excellence Multimodal Computing and Interaction Universität des Saarlandes Saarbrücken Germany Institut für Softwaretechnik und Theoretische Informatik TU Berlin Berlin Germany

We extend previous work on the parameterized complexity of local search for the Traveling Salesperson Problem (TSP). So far, its parameterized complexity has been investigated with respect to the distance measures (defining the local search area) "Edge Exchange" and "Max-Shift". We perform studies with respect to the distance measures "Swap" and "r-Swap", "Reversal" and "r-Reversal", and "Edit", achieving both fixed-parameter tractability and W[1]-hardness results. In particular, from the parameterized reduction showing W[1]-hardness we infer running time lower bounds (based on the exponential time hypothesis) for all corresponding distance measures. Moreover, we provide non-existence results for polynomial-size problem kernels and we show that some in general W[1]-hard problems turn fixed-parameter tractable when restricted to planar graphs. © 2012 Springer Science+Business Media, LLC.

关键词： Hardness

来源：评论

学校读者我要写书评

暂无评论

BiCluE - Exact and heuristic algorithms for weighted bi-cluster editing of biomedical data

引用

BMC proceedings 2013年第SUPPL 7期7卷 S9页

作者： Peng Sun Jiong Guo Jan Baumbach Computational Systems Biology Group Max Planck Institute for Informatics Saarbrücken Germany Cluster of Excellence for Multimodal Computing and Interaction Saarland University Saarbrücken Germany

BACKGROUND:The explosion of biological data has dramatically reformed today's biology research. The biggest challenge to biologists and bioinformaticians is the integration and analysis of large quantity of data to provide meaningful insights. One major problem is the combined analysis of data from different types. Bi-cluster editing, as a special case of clustering, which partitions two different types of data simultaneously, might be used for several biomedical scenarios. However, the underlying algorithmic problem is NP-hard. RESULTS:Here we contribute with BiCluE, a software package designed to solve the weighted bi-cluster editing problem. It implements (1) an exact algorithm based on fixed-parameter tractability and (2) a polynomial-time greedy heuristics based on solving the hardest part, edge deletions, first. We evaluated its performance on artificial graphs. Afterwards we exemplarily applied our implementation on real world biomedical data, GWAS data in this case. BiCluE generally works on any kind of data types that can be modeled as (weighted or unweighted) bipartite graphs. CONCLUSIONS:To our knowledge, this is the first software package solving the weighted bi-cluster editing problem. BiCluE as well as the supplementary results are available online at http://***.

关键词： Bipartite Graph Exact Algorithm Input Graph GWAS Data Edge Deletion

来源：评论

学校读者我要写书评

暂无评论

Incremental derivations in CCG 11

Incremental derivations in CCG

引用

11th International Workshop on Tree Adjoining Grammars and Related Formalisms, TAG+ 2012

作者： Demberg, Vera Cluster of Excellence Multimodal Computing and Interaction Saarland University Saarbrücken Germany

ISBN: (纸本)9781937284466

This paper presents a research note on the degree to which strictly incremental derivations (that is derivations which are fully connected at each point in time) are possible in Combinatory Categorial Grammar (CCG). There has been a recent surge of interest in incremental parsing both from the psycholinguistic community in a bid to build psycholinguistically plausible models of language comprehension, and from the NLP community for building systems that process language greedily in order to achieve shorter response times in spoken dialogue systems, for speech recognition and machine translation. CCG allows for a variety of different derivations, including derivations that are almost fully incremental. This paper explores the syntactic constructions for which full incrementality is not possible in standard CCG, a point that recent work on incremental CCG parsing has glossed over. © TAG+ *** right reserved.

关键词： Syntactics

来源：评论

学校读者我要写书评

暂无评论

A highly efficient GPU implementation for variational optic flow based on the Euler-Lagrange framework

A highly efficient GPU implementation for variational optic ...

引用

11th European Conference on Computer Vision, ECCV 2010

作者： Gwosdek, Pascal Zimmer, Henning Grewenig, Sven Bruhn, Andrés Weickert, Joachim Mathematical Image Analysis Group Faculty of Mathematics and Computer Science Saarland University Saarbrücken 66041 Germany Vision and Image Processing Group Cluster of Excellence Multimodal Computing and Interaction Saarland University Saarbrücken 66123 Germany

ISBN: (纸本)9783642357398

The Euler-Lagrange (EL) framework is the most widely-used strategy for solving variational optic flow methods. We present the first approach that solves the EL equations of state-of-the-art methods on sequences with pixels in near-realtime on GPUs. This performance is achieved by combining two ideas: (i) We extend the recently proposed Fast Explicit Diffusion (FED) scheme to optic flow, and additionally embed it into a coarse-to-fine strategy. (ii) We parallelise our complete algorithm on a GPU, where a careful optimisation of global memory operations and an efficient use of on-chip memory guarantee a good performance. Applying our approach to the variational 'Complementary Optic Flow' method (Zimmer et al. (2009)), we obtain highly accurate flow fields in less than a second. This currently constitutes the fastest method in the top 10 of the widely used Middlebury benchmark. © 2012 Springer-Verlag.

关键词： Graphics processing unit

来源：评论

学校读者我要写书评

暂无评论

Balls into Bins via Local Search 13

Balls into Bins via Local Search

引用

Symposium on Discrete Algorithms

作者： Paul Bogdan Thomas Sauerwald Alexandre Stauffer He Sun Department of Electrical and Computer Engineering Carnegie Mellon University Pittsburgh PA USA Max Planck Institute for Informatics Saarbrücken Germany and Cluster of Excellence "Multimodal Computing and Interaction" Universit?t des Saarlandes Saarbrücken Germany. Part of this work was done while visiting Microsoft Research Redmond Microsoft Research Redmond WA USA. Part of this work was done while visiting Max Planck Institute for Informatics Saarbrücken Germany. Max Planck Institute for Informatics Saarbrücken Germany and Institute of Modern Mathematics and Physics Fudan University Shanghai China.

ISBN: (纸本)9781627484855

We propose a natural process for allocating n balls into n bins that are organized as the vertices of an undirected graph G. Each ball first chooses a vertex u in G uniformly at random. Then the ball performs a local search in G starting from u until it reaches a vertex with local minimum load, where the ball is finally placed on. In our main result, we prove that this process yields a maximum load of only Θ (log log n) on expander graphs. In addition, we show that for d-dimensional grids the maximum load is Θ((log n/log log n)~(1/d+1)). Finally, for almost regular graphs with minimum degree Θ (logn), we prove that the maximum load is constant and also reveal a fundamental difference between random and arbitrary tie-breaking rules.

关键词： Balls into a maximum load fundamental difference Ball Device Component maximum loads Bins vertex head natural processes logs logarithm (log) undirected graph corners

来源：评论

学校读者我要写书评

暂无评论

Online transitivity clustering of biological data with missing values

Online transitivity clustering of biological data with missi...

引用

German Conference on Bioinformatics 2012, GCB 2012

作者： Röttger, Richard Kreutzer, Christoph Vu, Thuy Duong Wittkop, Tobias Baumbach, Jan Max Planck Institute for Informatics Saarbrücken Germany Center for Bioinformatics Saarbrücken Germany Cluster of Excellence on Multimodal Computing and Interaction Center for Bioinformatics Saarland University Saarbrücken Germany Bioinformatics Group CBS-KNAW Fungal Biodiversity Centre Utrecht Netherlands Buck Institute for Age Research Navato NV United States

ISBN: (纸本)9783939897446

Motivation: Equipped with sophisticated biochemical measurement techniques we generate a massive amount of biomedical data that needs to be analyzed computationally. One long-standing challenge in automatic knowledge extraction is clustering. We seek to partition a set of objects into groups such that the objects within the clusters share common traits. Usually, we have given a similarity matrix computed from a pairwise similarity function. While many approaches for biomedical data clustering exist, most methods neglect two important problems: (1) computing the similarity matrix might not be trivial but resource-intense. (2) A clustering algorithm itself is not sufficient for the biologist, who needs an integrated online system capable of performing preparative and follow-up tasks as well. Results: Here, we present a significantly extended version of Transitivity clustering. Our first main contribution is its' capability of dealing with missing values in the similarity matrix such that we save time and memory. Hence, we reduce one main bottleneck of computing all pairwise similarity values. We integrated this functionality into the Weighted Graph cluster Editing model underlying Transitivity clustering. By means of identifying protein (super)families from incomplete all-vs-all BLAST results we demonstrate the robustness of our approach. While most tools concentrate on the partitioning process itself, we present a new, intuitive web interface that aids with all important steps of a cluster analysis: (1) computing and post-processing of a similarity matrix, (2) estimation of a meaningful density parameter, (3) clustering, (4) comparison with given gold standards, and (5) fine-tuning of the clustering by varying the parameters. Availability: Transitivity clustering, the new Cost Matrix Creator, all used data sets as well as an online documentation are online available at http://***/. © Andreas Hoppe and Hermann-Georg Holzhütter.

关键词： clustering algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：