Genome assemblers to date have predominantly targeted haploid reference reconstruction from homozygous data. When applied to diploid genome assembly, these assemblers perform poorly, owing to the violation of assumptions during both the contigging and scaffolding phases. Effective tools to overcome these problems are in growing demand. Increasing parameter stringency during contigging is an effective solution to obtaining haplotype-specific contigs; however, effective algorithms for scaffolding such contigs are lacking.
Motivation: The contig orientation problem, which we formally define as the MAX-DIR problem, has at times been addressed cursorily and at times using various heuristics. In setting forth a linear-time reduction from the MAX-CUT problem to the MAX-DIR problem, we prove the latter is NP-complete. We compare the relative performance of a novel greedy approach with several other heuristic solutions. Results: Our results suggest that our greedy heuristic algorithm not only works well but also outperforms the other algorithms due to the nature of scaffold graphs. Our results also demonstrate a novel method for identifying inverted repeats and inversion variants, both of which contradict the basic single-orientation assumption. Such inversions have previously been noted as being difficult to detect and are directly involved in the genetic mechanisms of several diseases. Availability and implementation:http://bioresearch.byu.edu/scaffoldscaffolder. Contact:paulmbodily@gmail.com Supplementary information: Supplementary data are available at Bioinformatics online.
25 March 2022 in Transactions of the International Society for Music Information Retrieval
SUMMARY: Introgression is arguably one of the most important biological processes in the evolution of groups of related species, affecting at least 10% of the extant species in the animal kingdom. Introgression reduces genetic divergence between species, and in some cases can be highly beneficial, facilitating rapid adaptation to ever-changing environmental pressures. Introgression also significantly impacts inference of phylogenetic species relationships where a strictly binary tree model cannot adequately explain reticulate net-like species relationships. Here we use phylogenomic approaches to understand patterns of introgression along the evolutionary history of a unique, non-model insect system: dragonflies and damselflies (Odonata). We demonstrate that introgression is a pervasive evolutionary force across various taxonomic levels within Odonata. In particular, we show that the morphologically “intermediate” species of Anisozygoptera (one of the three primary suborders within Odonata besides Zygoptera and Anisoptera), which retain phenotypic characteristics of the other two suborders, experienced high levels of introgression likely coming from zygopteran genomes. Additionally, we found evidence for multiple cases of deep inter-superfamilial ancestral introgression.
Conway's law, the idea that a software system reflects the structure of the organization that built it, is one of the most well-known "laws" in software engineering. However, the seemingly straightforward phenomenon described by Conway appears to be subject to nuances of personal and organizational dynamics as well as contextual factors, most of which are neither well-understood nor well-studied. As a pilot study intended to foster discussion within the RESER community, we performed a small and somewhat informal qualitative study designed to elucidate some of these nuances. We posited that the designers' perception of the ultimate composition of the development team would affect the resultant system architecture more so than would the actual composition of the design team. The results of the pilot study support this hypothesis and are intended as a motivator for on-going discussion, as well as a catalyst for more thorough and formal differentiated replications, to explore and elucidate the nuances of Conway's law.
Whereas interactive dynamic visualization tools have been successfully developed and used for teaching some topics in computational theory (CT), there remains a noticeable lack of such tools for teaching NP-completeness which continues to be widely taught using paper-and-pencil methods. Despite its important theoretical and practical value, NP-completeness-and mapping reductions in NP-completeness in particular-tends to be a challenging concept for CT students to understand. We present an open-source web app called Redux that provides a dynamic interactive user interface atop a practical knowledge base of NP-complete problems, reductions, and solution algorithms. A key feature of the interface is the visualization of arbitrary problem instances, mapping reductions, solutions, and gadgets-including those reachable via transitivity. The web app is designed to make the knowledge base extensible, allowing students to contribute and compare their reductions and solutions to those already available. Two surveys were administered, with respondents overwhelmingly indicating that Redux helped them to better understand mapping reductions; that they would prefer using Redux to solve similar problems manually; and that Redux makes learning NP-complete reductions more enjoyable. Redux is accessible online via https://redux.portneuf.cose.isu.edu/.