To understand genome evolution in a group of microbes, we need to know the timing of events such as duplications, deletions and horizontal transfers. A common approach is to perform a gene-tree / species-tree reconciliation. While a number of software packages perform this type of analysis, none are geared toward a complete reconstruction for all families in an entire clade. Here we describe an update to the xenoGI software package which allows users to perform such an analysis using the newly developed DTLOR (duplication-transfer-loss-origin-rearrangement) reconciliation model starting from genome sequences as input.

Phylogenetic analyses commonly assume that the species history can be represented as a tree. However, in the presence of hybridization, the species history is more accurately captured as a network. Despite several advances in modeling phylogenetic networks, there is no known polynomial-time algorithm for parsimoniously reconciling gene trees with species networks while accounting for incomplete lineage sorting. To address this issue, we present a polynomial-time algorithm for the case of level-1 networks, in which no hybrid species is the direct ancestor of another hybrid species. This work enables more efficient reconciliation of gene trees with species networks, which in turn, enables more efficient reconstruction of species networks.

For a decade, our institution has offered both a biology-based CS1 (CS1-B) and a traditional, breadth-based CS1. This project follows the paths of students in both courses -- tracking their subsequent interests (what courses do the two groups choose afterwards') and their grades in those courses. Within the biology-based cohort, we also contrast the futures of the students who chose a biology-themed introduction with the group who expressed no preference or requested the breadth-based approach. Even when student preference was not accommodated, equitable downstream performance results hold. We discuss the implications of these results, including the possibility that, like introductory writing, introductory computing is a professional literacy in which many disciplines have a stake.

The maximum parsimony phylogenetic reconciliation problem seeks to explain incongruity between a gene phylogeny and a species phylogeny with respect to a set of evolutionary events. While the reconciliation problem is well-studied for species and gene trees subject to events such as duplication, transfer, loss, and deep coalescence, recent work has examined species phylogenies that incorporate hybridization and are thus represented by networks rather than trees. In this paper, we show that the problem of computing a maximum parsimony reconciliation for a gene tree and species network is NP-hard even when only considering deep coalescence. This result suggests that future work on maximum parsimony reconciliation for species networks should explore approximation algorithms and heuristics.

SUMMARY: We describe eMPRess, a software program for phylogenetic tree reconciliation under the duplication-transfer-loss model that systematically addresses the problems of choosing event costs and selecting representative solutions, enabling users to make more robust inferences. AVAILABILITY AND IMPLEMENTATION: eMPRess is freely available at http://www.cs.hmc.edu/empress. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Analyses of microbial evolution often use reconciliation methods. However, the standard duplication-transfer-loss (DTL) model does not account for the fact that species trees are often not fully sampled and thus, from the perspective of reconciliation, a gene family may enter the species tree from the outside. Moreover, within the genome, genes are often rearranged, causing them to move to new syntenic regions. RESULTS: We extend the DTL model to account for two events that commonly arise in the evolution of microbes: origin of a gene from outside the sampled species tree and rearrangement of gene syntenic regions. We describe an efficient algorithm for maximum parsimony reconciliation in this new DTLOR model and then show how it can be extended to account for non-binary gene trees to handle uncertainty in gene tree topologies. Finally, we describe preliminary experimental results from the integration of our algorithm into the existing xenoGI tool for reconstructing the histories of genomic islands in closely related bacteria. CONCLUSIONS: Reconciliation in the DTLOR model can offer new insights into the evolution of microbes that is not currently possible under the DTL model.

Gene trees can differ from species trees due to a variety of biological phenomena, the most prevalent being gene duplication, horizontal gene transfer, gene loss, and coalescence. To explain topological incongruence between the two trees, researchers apply reconciliation methods, often relying on a maximum parsimony framework. However, while several studies have investigated the space of maximum parsimony reconciliations (MPRs) under the duplication-loss and duplication-transfer-loss models, the space of MPRs under the duplication-loss-coalescence (DLC) model remains poorly understood. To address this problem, we present new algorithms for computing the size of MPR space under the DLC model and sampling from this space uniformly at random. Our algorithms are efficient in practice, with runtime polynomial in the size of the species and gene tree when the number of genes that map to any given species is fixed, thus proving that the MPR problem is fixed-parameter tractable. We have applied our methods to a biological data set of 16 fungal species to provide the first key insights in the space of MPRs under the DLC model. Our results show that a plurality reconciliation, and underlying events, are likely to be representative of MPR space.

Maximum parsimony reconciliation is a fundamental technique for studying the evolutionary histories of pairs of entities such as genes and species, parasites and hosts, and species and their biogeographical habitats. In these contexts, reconciliation is generally performed using the duplication-transfer-loss (DTL) model in a maximum parsimony framework. While efficient maximum parsimony reconciliation algorithms are known for the DTL model, the number of such reconciliations can grow exponentially with the sizes of the two phylogenetic trees. Choosing a maximum parsimony reconciliation arbitrarily may lead to conclusions that are not supported, and may even be contradicted, by other equally optimal reconciliations. This paper addresses the fundamental problem of how well a single reconciliation can represent the entire space of optimal reconciliations.

Typical CS 1 classes are about many things. The problems and examples are drawn from a variety of domains, with a goal of teaching a computational problem-solving approach and specific language constructs. Many CS 1 courses begin with writing programs that perform simple calculations, transition to more substantial simulations or games in the middle, and perhaps one or two SIGCSE Nifty Assignments at the end. In this panel, we explore the 'strongly-themed' approach in which many of the programs and examples used in the course come from a single domain which provides a theme for the course.

BACKGROUND: Maximum parsimony reconciliation in the duplication-transfer-loss model is a widely-used method for analyzing the evolutionary histories of pairs of entities such as hosts and parasites, symbiont species, and species and genes. While efficient algorithms are known for finding maximum parsimony reconciliations, the number of such reconciliations can be exponential in the size of the trees. Since these reconciliations can differ substantially from one another, making inferences from any one reconciliation may lead to conclusions that are not supported, or may even be contradicted, by other maximum parsimony reconciliations. Therefore, there is a need to find small sets of best representative reconciliations when the space of solutions is large and diverse. RESULTS: We provide a general framework for hierarchical clustering the space of maximum parsimony reconciliations. We demonstrate this framework for two specific linkage criteria, one that seeks to maximize the average support of the events found in the reconciliations in each cluster and the other that seeks to minimize the distance between reconciliations in each cluster. We analyze the asymptotic worst-case running times and provide experimental results that demonstrate the viability and utility of this approach. CONCLUSIONS: The hierarchical clustering algorithm method proposed here provides a new approach to find a set of representative reconciliations in the potentially vast and diverse space of maximum parsimony reconciliations.

BACKGROUND: Reconciliation methods are widely used to explain incongruence between a gene tree and species tree. However, the common approach of inferring maximum parsimony reconciliations (MPRs) relies on user-defined costs for each type of event, which can be difficult to estimate. Prior work has explored the relationship between event costs and maximum parsimony reconciliations in the duplication-loss and duplication-transfer-loss models, but no studies have addressed this relationship in the more complicated duplication-loss-coalescence model. RESULTS: We provide a fixed-parameter tractable algorithm for computing Pareto-optimal reconciliations and recording all events that arise in those reconciliations, along with their frequencies. We apply this method to a case study of 16 fungi to systematically characterize the complexity of MPR space across event costs and identify events supported across this space. CONCLUSION: This work provides a new framework for studying the relationship between event costs and reconciliations that incorporates both macro-evolutionary events and population effects and is thus broadly applicable across eukaryotic species.

BACKGROUND: Maximum parsimony reconciliation in the duplication-transfer-loss model is widely used in studying the evolutionary histories of genes and species and in studying coevolution of parasites and their hosts and pairs of symbionts. While efficient algorithms are known for finding maximum parsimony reconciliations, the number of reconciliations can grow exponentially in the size of the trees. An understanding of the space of maximum parsimony reconciliations is necessary to determine whether a single reconciliation can adequately represent the space or whether multiple representative reconciliations are needed. RESULTS: We show that for any instance of the reconciliation problem, the distribution of pairwise distances can be computed exactly by an efficient polynomial-time algorithm with respect to several different distance metrics. We describe the algorithm, analyze its asymptotic worst-case running time, and demonstrate its utility and viability on a large biological dataset. CONCLUSIONS: This result provides new insights into the structure of the space of maximum parsimony reconciliations. These insights are likely to be useful in the wide range of applications that employ reconciliation methods.

Phylogenetic tree reconciliation is widely used in the fields of molecular evolution, cophylogenetics, parasitology, and biogeography to study the evolutionary histories of pairs of entities. In these contexts, reconciliation is often performed using maximum parsimony under the Duplication-Transfer-Loss (DTL) event model. In general, the number of maximum parsimony reconciliations (MPRs) can grow exponentially with the size of the trees. While a number of previous efforts have been made to count the number of MPRs, find representative MPRs, and compute the frequencies of events across the space of MPRs, little is known about the structure of MPR space. In particular, how different are MPRs in terms of the events that they comprise? One way to address this question is to compute the diameter of MPR space, defined to be the maximum number of DTL events that distinguish any two MPRs in the solution space. We show how to compute the diameter of MPR space in polynomial time and then apply this algorithm to a large biological dataset to study the variability of events.

Phylogenetic tree reconciliation is an important technique for reconstructing the evolutionary histories of species and genes and other dependent entities. Reconciliation is typically performed in a maximum parsimony framework and the number of optimal reconciliations can grow exponentially with the size of the trees, making it difficult to understand the solution space. This paper demonstrates how a small number of reconciliations can be found that collectively contain the most highly supported events in the solution space. While we show that the formal problem is NP-complete, we give a approximation algorithm, experimental results that indicate its effectiveness, and the new DTL-RnB software tool that uses our algorithms to summarize the space of optimal reconciliations (www.cs.hmc.edu/dtlrnb).

BACKGROUND: Maximum parsimony phylogenetic tree reconciliation is an important technique for reconstructing the evolutionary histories of hosts and parasites, genes and species, and other interdependent pairs. Since the problem of finding temporally feasible maximum parsimony reconciliations is NP-complete, current methods use either exact algorithms with exponential worst-case running time or heuristics that do not guarantee optimal solutions. RESULTS: We offer an efficient new approach that begins with a potentially infeasible maximum parsimony reconciliation and iteratively "repairs" it until it becomes temporally feasible. CONCLUSIONS: In a non-trivial number of cases, this approach finds solutions that are better than those found by the widely-used Jane heuristic.

MOTIVATION: Phylogenetic tree reconciliation is a widely used method for reconstructing the evolutionary histories of gene families and species, hosts and parasites and other dependent pairs of entities. Reconciliation is typically performed using maximum parsimony, in which each evolutionary event type is assigned a cost and the objective is to find a reconciliation of minimum total cost. It is generally understood that reconciliations are sensitive to event costs, but little is understood about the relationship between event costs and solutions. Moreover, choosing appropriate event costs is a notoriously difficult problem. RESULTS: We address this problem by giving an efficient algorithm for computing Pareto-optimal sets of reconciliations, thus providing the first systematic method for understanding the relationship between event costs and reconciliations. This, in turn, results in new techniques for computing event support values and, for cophylogenetic analyses, performing robust statistical tests. We provide new software tools and demonstrate their use on a number of datasets from evolutionary genomic and cophylogenetic studies. AVAILABILITY AND IMPLEMENTATION: Our Python tools are freely available at www.cs.hmc.edu/∼hadas/xscape. .

Involving undergraduates in Computer Science research has many benefits. It's an exciting way for students to gain independent problem solving skills. It exposes them to interesting projects and the research process, thereby keeping them in computer science, even encouraging them to go to graduate school. And especially in primarily teaching institutions, it's a rewarding way for faculty to remain engaged in their own research. In this workshop we will (1) present best practices for mentoring undergraduate research, (2) equip participants with resources for mentoring their own students, and (3) further develop (1) and (2) through breakout sessions on concerns of interest to attendees. For more, please see www.cs.williams.edu/~andrea/SIGCSE2013. This workshop is intended for all college level computer science educators. Laptop Optional.

A common approach to teaching algorithms involves describing algorithms first and then proving their correctness afterwards. In this article we advocate a "derivation-first" approach in which algorithms are "derived," either from basic concepts or from simpler algorithms, before they are proved correct. We demonstrate how a number of "classical" algorithms can be derived, providing students with a more intellectually satisfying experience, a deeper intuition into how algorithm design works, and connections between algorithms that can be useful in developing algorithms for other problems.

We believe that undergraduate biology students must acquire a foundational background in computing including how to formulate a computational problem; develop an algorithmic solution; implement their solution in software and then test, document and use their code to explore biological phenomena. Moreover, by learning these skills in the first year, students acquire a powerful tool set that they can use and build on throughout their studies. To address this need, we have developed a first-year undergraduate course that teaches students the foundations of computational thinking and programming in the context of problems in biology. This article describes the structure and content of the course and summarizes assessment data on both affective and learning outcomes.

We present the curriculum, deployment, and initial evaluation of a course, BioCS1, designed to serve as an introductory course in both biology and CS. Co-taught by professors in both fields, BioCS1 interweaves fundamental biology and computational topics in a manner similar to contextual approaches to CS1. In contrast to other contextual approaches, however, BioCS1 emphasizes both CS and its context equally. The results suggest that such cross-disciplinary collaborations can thrive at the introductory level, just as they have later in the curriculum.

We present the curriculum, deployment, and initial evaluation of a course, BioCS1, designed to serve as CS1 and Biology1 for majors of either (or both) disciplines. Cotaught by professors in both fields, BioCS1 interweaves fundamental biology and computational topics in a manner similar to contextual approaches to CS1. In contrast to other contextual approaches, however, BioCS1 emphasizes both CS and its context equally. The results suggest that cross-disciplinary collaborations can succeed at the introductory level, as they have at later stages of the curriculum.

This paper addresses the problem of traffic grooming in WDM rings in which all traffic emanates from a single node and all other nodes are destination nodes. This "one-to-many" scenario arises in metropolitan access networks in which one node serves as a "hub" connecting the ring to a larger network as well as in video-on-demand and other multimedia services where a single source node serves a collection of subscriber nodes. The ring comprises a given number of wavelengths of uniform capacity and a variable number of tunable add-drop multiplexers (ADMs) at each node. Given a set of requests at the destination nodes, where each request comprises a bandwidth demand and a profit for fulfilling the request, our objective is to select a subset of the requests and pack ("groom") them onto the wavelengths such that no wavelength's capacity is exceeded and the total profit of the selected requests is maximized. Although this problem is NP-complete, we give polynomial time approximation algorithms with excellent theoretical performance validated with experimental results.

This paper presents a thorough evaluation of CS for Scientists, a CS 1 course designed to provide future scientists with an overview of the discipline. The course takes a breadth-first approach that leverages its students' interest and experience in science, mathematics, and engineering. In contrast to many other styles of CS 1, this course does not presume that its students will study more computer science, but it does seek to prepare them should they choose to. We summarize the past year's worth of assessments of student learning, retention, and affect -- with particular attention paid to women's voices. Where possible, we contrast these student measures with those from a traditional, imperative-first CS1 that this new course replaced. The data thus far suggest that CS for Scientists significantly improves students' understanding of CS, its applications, and practice.

This paper describes an introductory CS course designed to provide future scientists with a one-semester overview of the discipline. The course takes a breadth-first approach that leverages its students' interest and experience in science, mathematics, and engineering. In contrast to many other styles of CS 1, this course does not presume that its students will study more computer science, but it does seek to prepare them should they choose to do so. In addition to describing the curriculum and resources, we summarize our preliminary assessments of this course and a comparison with the more traditional, imperative-first introduction it replaced. The data thus far suggest that this CS for Scientists course improves our students' understanding of CS, its applications, and practice.

We consider the problem of minimizing the number of ADMs for single-source multicast communication in WDM rings using traffic grooming. We examine two distinct models of communication, one permitting the same message to be sent on multiple distinct wavelengths and one each message to be sent exactly once. The problem of minimizing the number of ADMs is shown to be NP-complete in the strong sense for both models. However, we are able to solve a special case in polynomial time and provide good approximation algorithms and heuristics for the remaining cases. These approximation algorithms and heuristics are validated both theoretically and experimentally.

This paper investigates the problem of finding optimal multicast virtual topologies, with respect to minimizing the maximum hop distance, in wavelength-division multiplexing multicast trees. Although the problem of finding optimal multicast trees is itself known to be NP-complete under many optimization metrics, high-quality approximation algorithms are known for this problem. We investigate the case that a multicast tree has been selected and seek to embed an optimal virtual topology in this multicast tree. We show that the problem can be solved in polynomial time when tap-and-continue switches are employed, which allow a lightpath to be tapped by some number of intermediate nodes. However, the problem becomes NP-complete when fully multicast-capable switches are employed. Our results suggest that tap-and-continue switches can be used to obtain high-quality multicast virtual topologies, while heuristics will be required to find good solutions in fully multicast-capable networks.

In this paper we examine the problem of constructing optimal virtual topologies for one-to-many communication in optical networks employing wavelength-division multiplexing. A virtual topology is a collection of optical lightpaths embedded in a physical topology. A packet sent from the source node travels over one or more lightpaths en route to its destination. Within a lightpath, transmission is entirely optical. At the terminus of a lightpath the data is converted into the electronic domain where it may be retransmitted on another lightpath toward its destination. Since the conversion of the packet from the optical to the electronic domain introduces delays and uses limited physical resources, one important objective is to find virtual topologies which minimize either the maximum or average number of lightpaths used from the source to all destination nodes. Although this problem is NP-complete in general, we show that minimizing the maximum or average number of lightpaths in path and ring topologies can be solved optimally by efficient algorithms.

This paper addresses the problem of constructing optimal virtual topologies for multicast communication in optical networks employing wavelength-division multiplexing (WDM). For concreteness, we use the average hop distance as the metric of optimality. WDM networks supporting multicast communication typically employ multicast-capable switches which permit a path entering a switch on an incoming wavelength to be replicated or "split" optically to one or more output links. This splitting incurs a power loss which is frequently neglected in existing heuristics and algorithms. In this paper we show that the problem of finding optimal virtual topologies with splitting loss constraints can be solved in polynomial time in directed paths and rings, although the problem is NP-complete for general topologies.

This paper addresses multicast routing in circuit-switched multihop optical networks employing wavelength-division multiplexing. We consider a model in which multicast communication requests are made and released dynamically over time. A multicast connection is realized by constructing a multicast tree which distributes the message from the source node to all destination nodes such that the wavelengths used on each link and the receivers and transmitters used at each node are not used by existing circuits. We show that the problem of routing and wavelength assignment in this model is, in general, NP-complete. However, we also show that for any given multicast tree, the wavelength assignment problem can be solved in linear time.

This paper addresses the problem of efficient multicast communication in wavelength-division multiplexed optical networks. In particular, we consider all-optical networks in which each transmitting node may deliver its message to some fixed number of destination nodes on a light path. The number of destination nodes that may receive the message using a single path depends on the power budget of the transmitting node. We study the wavelength requirements for multicast communication under this model.

Wormhole routing is widely employed in current generation multicomputers and the design of deadlock-free wormhole routing algorithms is an important problem. In this note, we prove a tight lower bound on the number of channels required by a broad class of deadlockfree wormhole routing algorithms. This result has applications in proving that certain topologies do not admit deadlock-free wormhole routing algorithms, as well as applications in the design and analysis of fault-tolerant wormhole routing algorithms.

This paper addresses the problem of fault-tolerant multicast routing in wormhole-routed multicomputers. We present a new pseudo-Hamiltonian path-based routing methodology for constructing deadlock-free multicast routing algorithms requiring no virtual channels. This technique is applied to construct the first fault-tolerant multicast routing algorithm for the mesh that requires no virtual channels. Simulation results indicate that this technique results in minimal performance degradation in the presence of a large number of node and channel faults.

The ability to tolerate faults is critical in multi-computers employing large numbers of processors. This paper describes a class of fault-tolerant routing algorithms for n-dimensional meshes that can tolerate large numbers of faults without using virtual channels. We show that these routing algorithms prevent livelock and deadlock while remaining highly adaptive.>

In this paper we consider the problem of reconfiguring processor arrays subject to computational loads that alternate between two modes. A strict mode is characterized by a heavy computational load and severe constraints on response time while a relaxed mode is characterized by a relatively light computational load and relaxed constraints on response time. In the strict mode, reconfiguration is performed by a distributed local algorithm in order to achieve fast recovery from faults. In the relaxed mode, a global reconfiguration algorithm is used to restore the system to a state that maximizes the probability that future faults occurring in subsequent strict modes will be repairable. Several new results are given for this problem. Efficient reconfiguration algorithms are described for a number of general classes of architectures. These general algorithms obviate the need for architecture-specific algorithms for architectures in these classes. We show that it is unlikely that similar algorithms can be obtained for related classes of architectures since the reconfiguration problem for these classes is NP-complete. Finally, a general approximation algorithm is described that can be used for any architecture. Experimental results are given, suggesting that our algorithms are very effective.>

Reconfigurable chips are fabricated with redundant elements that can be used to replace the faulty elements. The fault cover problem consists of finding an assignment of redundant elements to the faulty elements such that all of the faults are repaired. In reconfigurable chips that consist of arrays of elements, redundant elements are configured as spare rows and spare columns. This paper considers the problem in which a chip contains several replicates of a heterogeneous array, one or more sets of spare rows, and one or more sets of spare columns. Each set of spare rows is identical to the set of rows in the array, and each set of spare columns is identical to the set of columns in the array. Specifically, an ith spare row can only be used to replace an ith row of an array, and similarly with spare columns. Repairing the chip reduces to finding a cover for the faults in each of the arrays. These covers must be disjoint; that is, a particular spare row or spare column can be used in the cover of at most one array. Results are presented for three fault cover problems that arise under these conditions.

In this paper we study two strategies for modifying a given placement of modules in order to improve the quality of the routing results in the next stage of design. We assume that the modules have already been placed. The first strategy seeks to minimize the total wire length by flipping each module about its vertical and/or horizontal axes of symmetry. The second strategy seeks to minimize the total wire length by rotating each module by a multiple of 90 degrees. We introduce a new algorithm based on the Hopfield-Tank neural-net model to solve these problems. Our algorithm performs better than the best algorithms known for these problems. Both problems are shown to be NP-Complete.