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

Forbidden time travel: Characterization of time-consistent tree reconciliation maps 17

学校读者我要写书评

暂无评论

Forbidden time travel: Characterization of time-consistent t...

17th International Workshop on Algorithms in Bioinformatics, WABI 2017

作者： Nøjgaard, Nikolai Geiß, Manuela Merkle, Daniel Stadler, Peter F. Wieseke, Nicolas Hellmuth, Marc Department of Mathematics and Computer Science University of Greifswald Greifswald Germany Department of Mathematics and Computer Science University of Southern Denmark Denmark Bioinformatics Group Department of Computer Science Interdisciplinary Center of Bioinformatics University of Leipzig Leipzig Germany Max-Planck-Institute for Mathematics in the Sciences Leipzig Germany Institute for Theoretical Chemistry University of Vienna Vienna Austria Santa Fe Institute Santa FeNM United States Parallel Computing and Complex Systems Group Department of Computer Science Leipzig University Leipzig Germany Saarland University Center for Bioinformatics Saarbrücken Germany

ISBN: (纸本)9783959770507

Motivation: In the absence of horizontal gene transfer it is possible to reconstruct the history of gene families from empirically determined orthology relations, which are equivalent to eventlabeled gene trees. Knowledge of the event labels considerably simplifies the problem of reconciling a gene tree T with a species trees S, relative to the reconciliation problem without prior knowledge of the event types. It is well-known that optimal reconciliations in the unlabeled case may violate time-consistency and thus are not biologically feasible. Here we investigate the mathematical structure of the event labeled reconciliation problem with horizontal transfer. Results: We investigate the issue of time-consistency for the event-labeled version of the reconciliation problem, provide a convenient axiomatic framework, and derive a complete characterization of time-consistent reconciliations. This characterization depends on certain weak conditions on the event-labeled gene trees that reflect conditions under which evolutionary events are observable at least in principle. We give an O(|V (T)| log(|V (S)|))-time algorithm to decide whether a time-consistent reconciliation map exists. It does not require the construction of explicit timing maps, but relies entirely on the comparably easy task of checking whether a small auxiliary graph is acyclic. Significance: The combinatorial characterization of time consistency and thus biologically feasible reconciliation is an important step towards the inference of gene family histories with horizontal transfer from orthology data, i.e., without presupposed gene and species trees. The fast algorithm to decide time consistency is useful in a broader context because it constitutes an attractive component for all tools that address tree reconciliation problems. © Nikolai Nøjgaard, Manuela Geiß, Daniel Merkle, Peter F. Stadler, Nicolas Wieseke, and Marc Hellmuth.

关键词： Genes

SPECTRE: Supporting consumption policies in window-based parallel complex event processing

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Mayer, Ruben Slo, Ahmad Tariq, Muhammad Adnan Rothermel, Kurt Gräber, Manuel Ramachandran, Umakishore Institute of Parallel and Distributed Systems University of Stuttgart Department of Computer Science Fast - National University of Computer and Emerging Sciences Islamabad Pakistan College of Computing Georgia Institute of Technology United States

distributed Complex Event Processing (DCEP) is a paradigm to infer the occurrence of complex situations in the surrounding world from basic events like sensor readings. In doing so, DCEP operators detect event patterns on their incoming event streams. To yield high operator throughput, data parallelization frameworks divide the incoming event streams of an operator into overlapping windows that are processed in parallel by a number of operator instances. In doing so, the basic assumption is that the different windows can be processed independently from each other. However, consumption policies enforce that events can only be part of one pattern instance;then, they are consumed, i.e., removed from further pattern detection. That implies that the constituent events of a pattern instance detected in one window are excluded from all other windows as well, which breaks the data parallelism between different windows. In this paper, we tackle this problem by means of speculation: Based on the likelihood of an event's consumption in a window, subsequent windows may speculatively suppress that event. We propose the SPECTRE framework for speculative processing of multiple dependent windows in parallel. Our evaluations show an up to linear scalability of SPECTRE with the number of CPU cores. Copyright © 2017, The Authors. All rights reserved.

关键词： Data handling

Eunomia: Scaling Concurrent Search Trees under Contention Using HTM

学校读者我要写书评

暂无评论

ACM SIGPLAN Notices 2017年第8期52卷 385-399页

作者： Wang, Xin Zhang, Weihua Wang, Zhaoguo Wei, Ziyun Chen, Haibo Zhao, Wenyun Software School Fudan University China Shanghai Key Laboratory of Data Science Fudan University School of Computer Science Fudan University China Institute of Parallel and Distributed Systems Shanghai Jiao Tong University China Computer Science Department New York University United States

While hardware transactional memory (HTM) has recently been adopted to construct efficient concurrent search tree structures, such designs fail to deliver scalable performance under contention. In this paper, we first conduct a detailed analysis on an HTM-based concurrent B+Tree, which uncovers several reasons for excessive HTM aborts induced by both false and true conflicts under contention. Based on the analysis, we advocate Eunomia, a design pattern for search trees which contains several principles to reduce HTM aborts, including splitting HTM regions with version-based concurrency control to reduce HTM working sets, partitioned data layout to reduce false conflicts, proactively detecting and avoiding true conflicts, and adaptive concurrency control. To validate their effectiveness, we apply such designs to construct a scalable concurrent B+Tree using HTM. Evaluation using key-value store benchmarks on a 20-core HTM-capable multi-core machine shows that Eunomia leads to 5X-11X speedup under high contention, while incurring small overhead under low contention. © 2017 ACM.

关键词： Concurrency control

Using English as pivot to extract Persian-Italian parallel sentences from non-parallel corpora

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Ansari, Ebrahim Sadreddini, M.H. Sheikhalishahi, Mostafa Wallace, Richard Alimardani, Fatemeh Zanjan Iran Department of Computer Science and Engineering Shiraz University Shiraz Iran Department of Mathematics and Informatics University of Calabria Rende Italy Distributed Systems Architecture Research Group Complutense University Madrid Spain

The effectiveness of a statistical machine translation system (SMT) is very dependent upon the amount of parallel corpus used in the training phase. For low-resource language pairs there are not enough parallel corpora to build an accurate SMT. In this paper, a novel approach is presented to extract bilingual Persian-Italian parallel sentences from a non-parallel (comparable) corpus. In this study, English is used as the pivot language to compute the matching scores between source and target sentences and candidate selection phase. Additionally, a new monolingual sentence similarity metric, Normalized Google Distance (NGD) is proposed to improve the matching process. Moreover, some extensions of the baseline system are applied to improve the quality of extracted sentences measured with BLEU. Experimental results show that using the new pivot based extraction can increase the quality of bilingual corpus significantly and consequently improves the performance of the Persian-Italian SMT system. Copyright © 2017, The Authors. All rights reserved.

关键词： computer aided language translation

Generic Context Adaptation for Mobile Cloud Computing Environments

学校读者我要写书评

暂无评论

Procedia computer science 2016年 94卷 17-24页

作者： Gabriel Orsini Dirk Bade Winfried Lamersdorf Distributed Systems Group Department of Computer Science University of Hamburg Germany

Markets for mobile applications offer myriads of apps ranging from simple to quite demanding ones. The latter are on the rise since every new generation of smartphones is equipped with more resources (CPU, memory, bandwidth, energy) to even allow resource-demanding services like speech- or face recognition to be executed locally on a device. But compared to their stationary counterparts, mobile devices remain comparatively limited in terms of resources. Because of this, current approaches aim at extending mobile device capabilities with computation and storage resources offered by cloud services or other nearby devices. This paradigm, known as Mobile Cloud Computing (MCC), is challenged by the dynamically changing context of mobile devices, which developers are required to take into account to decide, e.g., which application parts are when to offload. To rise to such and similar challenges we introduce the concept of Generic Context Adaptation (GCA), a data mining process that facilitates the adaptation of (mobile) applications to their current and future context. Moreover, we evaluate our approach with real usage data provided by the Nokia Mobile Data Challenge (MDC) as well as with CloudAware , a context-adaptive mobile middleware for MCC that supports automated context-aware self-adaptation techniques.

关键词： Mobile Cloud Computing Mobile Edge Computing Context Adaptation Context Awareness

Rapid mobile development with ARC: Application framework for robust communications for disaster risk reduction and management 12

学校读者我要写书评

暂无评论

Rapid mobile development with ARC: Application framework for...

12th IEEE International Conference on Wireless and Mobile Computing, Networking and Communications, WiMob 2016

作者： Santos, Jan Vincent Torres, Danah Veronica Villanoy, Monica Kathrina Festin, Cedric Angelo Doctor, John Norman Ocampo, Roel Networks and Distributed Systems Group Department of Computer Science University of the Philippines Philippines Computer Networks Laboratory Electrical and Electronics Engineering Institute University of the Philippines Philippines

ISBN: (纸本)9781509007240

In disaster situations communication and power infrastructure could be damaged, disrupting their associated services. This could delay relief efforts and cost more lives. In situations where connections are damaged and unreliable, peer-to-peer (P2P) and delay-tolerant networking (DTN) technologies can help provide alternative communication modes particularly in support of rescue and relief operations. Combining the benefits of the store-and-forward capability of DTN and the data propagation techniques of Wi-Fi Direct, we have created a flexible framework called ARC which allows users to create applications that could meet their specific requirements, particularly those in support of emergency communications. To demonstrate our framework, we created a simple application using ARC, and used this application to evaluate its DTN and Wi-Fi Direct group recovery capabilities. © 2016 IEEE.

关键词： Wireless local area networks (WLAN)

Forbidden time travel: Characterization of time-consistent tree reconciliation maps

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Nøjgaard, Nikolai Geiß, Manuela Stadler, Peter F. Merkle, Daniel Wieseke, Nicolas Hellmuth, Marc Dpt. of Mathematics and Computer Science University of Greifswald Walther- Rathenau-Strasse 47 GreifswaldD-17487 Saarland University Center for Bioinformatics Building e 2.1 P.O. Box 151150 SaarbrückenD-66041 Bioinformatics Group Department of Computer Science Interdisciplinary Center of Bioinformatics University of Leipzig Härtelstraße 16-18 LeipzigD-04107 Germany Department of Mathematics and Computer Science University of Southern Denmark Max-Planck-Institute for Mathematics in the Sciences Inselstraße 22 LeipzigD-04103 Germany Inst. F. Theoretical Chemistry University of Vienna Währingerstraße 17 WienA-1090 Austria Santa Fe Institute 1399 Hyde Park Rd. Santa Fe United States Parallel Computing and Complex Systems Group Department of Computer Science Leipzig University Augustusplatz 10 Leipzig04109 Germany

Motivation: In the absence of horizontal gene transfer it is possible to reconstruct the history of gene families from empirically determined orthology relations, which are equivalent to eventlabeled gene trees. Knowledge of the event labels considerably simplifies the problem of reconciling a gene tree T with a species trees S, relative to the reconciliation problem without prior knowledge of the event types. It is well-known that optimal reconciliations in the unlabeled case may violate time-consistency and thus are not biologically feasible. Here we investigate the mathematical structure of the event labeled reconciliation problem with horizontal transfer. Results: We investigate the issue of time-consistency for the event-labeled version of the reconciliation problem, provide a convenient axiomatic framework, and derive a complete characterization of time-consistent reconciliations. This characterization depends on certain weak conditions on the event-labeled gene trees that reflect conditions under which evolutionary events are observable at least in principle. We give an O(|V(T)|log(|V (S)|))-time algorithm to decide whether a time-consistent reconciliation map exists. It does not require the construction of explicit timing maps, but relies entirely on the comparably easy task of checking whether a small auxiliary graph is acyclic. Significance: The combinatorial characterization of time consistency and thus biologically feasible reconciliation is an important step towards the inference of gene family histories with horizontal transfer from orthology data, i.e., without presupposed gene and species trees. The fast algorithm to decide time consistency is useful in a broader context because it constitutes an attractive component for all tools that address tree reconciliation problems. Copyright © 2017, The Authors. All rights reserved.

关键词： Genes

Reconstructing gene trees from Fitch's xenology relation

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Geiß, Manuela Anders, John Stadler, Peter F. Wieseke, Nicolas Hellmuth, Marc Bioinformatics Group Department of Computer Science Interdisciplinary Center of Bioinformatics University of Leipzig Härtelstraße 16-18 LeipzigD-04107 Germany Dpt. of Mathematics and Computer Science University of Greifswald Walther- Rathenau-Strasse 47 GreifswaldD-17487 Germany Saarland University Center for Bioinformatics Building E 2.1 P.O. Box 151150 SaarbrückenD-66041 Germany Max-Planck-Institute for Mathematics in the Sciences Inselstraße 22 LeipzigD-04103 Germany Inst. f. Theoretical Chemistry University of Vienna Währingerstraße 17 WienA-1090 Austria Santa Fe Institute 1399 Hyde Park Rd. Santa Fe United States Parallel Computing and Complex Systems Group Department of Computer Science Leipzig University Augustusplatz 10 Leipzig04109 Germany

Two genes are xenologs in the sense of Fitch if they are separated by at least one horizontal gene transfer event. Horizonal gene transfer is asymmetric in the sense that the transferred copy is distinguished from the one that remains within the ancestral lineage. Hence xenology is more precisely thought of as a non-symmetric relation: y is xenologous to x if y has been horizontally transferred at least once since it diverged from the least common ancestor of x and y. We show that xenology relations are characterized by a small set of forbidden induced subgraphs on three vertices. Furthermore, each xenology relation can be derived from a unique least-resolved edge-labeled phylogenetic tree. We provide a linear-time algorithm for the recognition of xenology relations and for the construction of its least-resolved edge-labeled phylogenetic tree. The fact that being a xenology relation is a heritable graph property, finally has far-reaching consequences on approximation problems associated with xenology relations. Copyright © 2017, The Authors. All rights reserved.

关键词： Clustering algorithms

From event labeled gene trees to species trees

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Hernandez-Rosales, Maribel Hellmuth, Marc Wieseke, Nicolas Huber, Katharina T. Moulton, Vincent Stadler, Peter F. Dpt. of Mathematics and Computer Science University of Greifswald Walther- Rathenau-Strasse 47 GreifswaldD-17487 Saarland University Center for Bioinformatics Building e 2.1 P.O. Box 151150 SaarbrückenD-66041 Bioinformatics Group Department of Computer Science Interdisciplinary Center of Bioinformatics University of Leipzig Härtelstraße 16-18 LeipzigD-04107 Germany School of Computing Sciences University of East Anglia NorwichNR4 7TJ United Kingdom Max-Planck-Institute for Mathematics in the Sciences Inselstraße 22 LeipzigD-04103 Germany Inst. F. Theoretical Chemistry University of Vienna Währingerstraße 17 WienA-1090 Austria Santa Fe Institute 1399 Hyde Park Rd. Santa Fe United States Parallel Computing and Complex Systems Group Department of Computer Science Leipzig University Augustusplatz 10 Leipzig04109 Germany

Background: Tree reconciliation problems have long been studied in phylogenetics. A particular variant of the reconciliation problem for a gene tree T and a species tree S assumes that for each interior vertex x of T it is known whether x represents a speciation or a duplication. This problem appears in the context of analyzing orthology data. Results: We show that S is a species tree for T if and only if S displays all rooted triples of T that have three distinct species as their leaves and are rooted in a speciation vertex. A valid reconciliation map can then be found in polynomial time. Simulated data shows that the event-labeled gene trees convey a large amount of information on underlying species trees, even for a large percentage of losses. Conclusions: The knowledge of event labels in a gene tree strongly constrains the possible species tree and, for a given species tree, also the possible reconciliation maps. Nevertheless, many degrees of freedom remain in the space of feasible solutions. In order to disambiguate the alternative solutions additional external constraints as well as optimization criteria could be employed. Copyright © 2017, The Authors. All rights reserved.

关键词： Polynomial approximation