A phylogenetic network is a generalization of a phylogenetic tree, allowing structural properties that are not treelike. With the growth of genomic data, much of which does not fit ideal tree models, there is greater ...
详细信息
ISBN:
(纸本)0769520006
A phylogenetic network is a generalization of a phylogenetic tree, allowing structural properties that are not treelike. With the growth of genomic data, much of which does not fit ideal tree models, there is greater need to understand the algorithmics and combinatorics of phylogenetic networks [10, 11]. However, to date, very little has been published on this, with the notable exception of the paper by Wang et al.[12]. Other related papers include [4, 5, 7] We consider the problem introduced in [12], of determining whether the sequences can be derived on a phylogenetic network where the recombination cycles are node disjoint. In this paper, we call such a phylogenetic network a "galled-tree". By more deeply analysing the combinatorial constraints on cycle-disjoint phylogenetic networks, we obtain an efficient algorithm that is guaranteed to be both a necessary and sufficient test for the existence of a galled tree for the data. If there is a galled-tree, the algorithm constructs one and obtains an implicit representation of all the galled trees for the data, and can create these in linear time for each one. We also note two additional results related to galled trees: first, any set of sequences that can be derived on a galled tree can be derived on a true tree (without recombination cycles), where at most one back mutation is allowed per site;second, the site compatibility problem (which is NP-hard in general) can be solved in linear time for any set of sequences that can be derived on a galled tree. The combinatorial constraints we develop apply (for the most part) to node-disjoint cycles in any phylogenetic network (not just galled-trees), and can be used for example to prove that a given site cannot be on a node-disjoint cycle in any phylogenetic network. Perhaps more important than the specific results about galled-trees, we introduce an approach that can be used to study recombination in phylogenetic networks that go beyond galled-trees.
The proceedings contain 36 papers. The special focus in this conference is on Formal Approaches to Agent-Based systems. The topics include: A state chart framework for agent roles that captures expertise and learns im...
ISBN:
(纸本)9783540406655
The proceedings contain 36 papers. The special focus in this conference is on Formal Approaches to Agent-Based systems. The topics include: A state chart framework for agent roles that captures expertise and learns improved behavior;formal specification of interaction in agent societies;formal verification for a next-generation space shuttle;towards interaction protocol operations for large multi-agent systems;formal modeling and supervisory control of reconfigurable robot teams;computational models for multiagent coordination analysis;bounded model checking for interpreted systems;verifiable middleware for secure agent interoperability;distributed implementation of a connection graph based on cylindric set algebra operators;using state charts and modal logics to model multiagent plans and transactions;an implementation language for agents with advanced reasoning capabilities;a model for conformance testing of mobile agents in a MASIF framework;analysis of a phase transition in a physics-based multiagent system;taking intelligent agents to the battlefield;naval applications of secure multi-agent technology;using xml for interprocess communications in a space situational awareness and control application;challenges arising from applications of agent-based system;tools and education towards formal methods practice;evaluating agent-based modeling as a tool for economists;towards a formal representation of driving behaviors;formal analysis of an agent-based medical diagnosis confirmation system and agent programming in dribble.
The proceedings contain 17 papers. The special focus in this conference is on Object Middleware, Resource Discovery and Management. The topics include: Grid application design using software components and web service...
ISBN:
(纸本)3540429492
The proceedings contain 17 papers. The special focus in this conference is on Object Middleware, Resource Discovery and Management. The topics include: Grid application design using software components and web services;design and implementation of a CORBA commodity grid kit;towards high performance CORBA and MPI middlewares for grid computing;an integrated grid environment for component applications;high performance knowledge discovery on the grid;on fully decentralized resource discovery in grid environments;an adaptive service grid architecture using dynamic replica management;identifying dynamic replication strategies for a high-performance datagrid;resource co-allocation on the computational grid;a computational grid-wide queuing system;a scheduling model for grid computing systems;encapsulated approaches to grid service architecture;a methodology for account management in grid computing environments;a framework for authorization, accounting policy specification and evaluation in grids;predicting and monitoring grid application behavior;production-level distributed parametric study capabilities for the grid and the DO experiment data grid.
暂无评论