MetaSMC: a coalescent-based shotgun sequence simulator for evolving microbial populations.

MOTIVATION: High-throughput sequencing technology has revolutionized the study of metagenomics and cancer evolution. In a relatively simple environment, a metagenomics sequencing data is dominated by a few species. By analyzing the alignment of reads from microbial species, single nucleotide polymorphisms can be discovered and the evolutionary history of the populations can be reconstructed. The ever-increasing read length will allow more detailed analysis about the evolutionary history of microbial or tumor cell population. A simulator of shotgun sequences from such populations will be helpful in the development or evaluation of analysis algorithms. RESULTS: Here, we described an efficient algorithm, MetaSMC, which simulates reads from evolving microbial populations. Based on the coalescent theory, our simulator supports all evolutionary scenarios supported by other coalescent simulators. In addition, the simulator supports various substitution models, including Jukes-Cantor, HKY85 and generalized time-reversible models. The simulator also supports mutator phenotypes by allowing different mutation rates and substitution models in different subpopulations. Our algorithm ignores unnecessary chromosomal segments and thus is more efficient than standard coalescent when recombination is frequent. We showed that the process behind our algorithm is equivalent to Sequentially Markov Coalescent with an incomplete sample. The accuracy of our algorithm was evaluated by summary statistics and likelihood curves derived from Monte Carlo integration over large number of random genealogies. AVAILABILITY AND IMPLEMENTATION: MetaSMC is written in C. The source code is available at https://github.com/tarjxvf/metasmc. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Application of 16S rRNA metagenomics to analyze bacterial communities at a respiratory care centre in Taiwan.

In this study, we applied a 16S ribosomal RNA (rRNA) metagenomics approach to survey inanimate hospital environments (IHEs) in a respiratory care center (RCC). A total of 16 samples, including 9 from medical devices and 7 from workstations, were analyzed. Besides, clinical isolates were retrospectively analyzed during the sampling period in the RCC. A high amount of microbial diversity was detected, with an average of 1,836 phylotypes per sample. In addition to Acinetobacter, more than 60 % of the bacterial communities present among the top 25 abundant genera were dominated by skin-associated bacteria. Differences in bacterial profiles were restricted to individual samples. Furthermore, compliance with hand hygiene guidelines may be unsatisfactory among hospital staff according to a principal coordinate analysis that indicated clustering of bacterial communities between devices and workstations for most of the sampling sites. Compared to the high incidence of clinical isolates in the RCC, only Staphylococcus and Acinetobacter were highly abundant in the IHEs. Despite Acinetobacter was the most abundant genus present in IHEs of the RCC, potential pathogens, e.g., Acinetobacter baumannii, might remain susceptible to carbapenem. This study is the first in Taiwan to demonstrate a high diversity of human-associated bacteria in the RCC via 16S rRNA metagenomics, which allows for new assessment of potential health risks in RCCs, aids in the evaluation of existing sanitation protocols, and furthers our understanding of the development of healthcare-associated infections.

RNASAlign: RNA structural alignment system.

MOTIVATION: Structural alignment of RNA is found to be a useful computational technique for idenitfying non-coding RNAs (ncRNAs). However, existing tools do not handle structures with pseudoknots. Although algorithms exist that can handle structural alignment for different types of pseudoknots, no software tools are available and users have to determine the type of pseudoknots to select the appropriate algoirthm to use which limits the usage of structural alignment in identifying novel ncRNAs. RESULTS: We implemented the first web server, RNASAlign, which can automatically identify the pseudoknot type of a secondary structure and perform structural alignment of a folded RNA with every region of a target DNA/RNA sequence. Regions with high similarity scores and low e-values, together with the detailed alignments will be reported to the user. Experiments on more than 350 ncRNA families show that RNASAlign is effective. AVAILABILITY: http://www.bio8.cs.hku.hk/RNASAlign.

Ψ-RA: a parallel sparse index for genomic read alignment.

BACKGROUND: Genomic read alignment involves mapping (exactly or approximately) short reads from a particular individual onto a pre-sequenced reference genome of the same species. Because all individuals of the same species share the majority of their genomes, short reads alignment provides an alternative and much more efficient way to sequence the genome of a particular individual than does direct sequencing. Among many strategies proposed for this alignment process, indexing the reference genome and short read searching over the index is a dominant technique. Our goal is to design a space-efficient indexing structure with fast searching capability to catch the massive short reads produced by the next generation high-throughput DNA sequencing technology. RESULTS: We concentrate on indexing DNA sequences via sparse suffix arrays (SSAs) and propose a new short read aligner named Ψ-RA (PSI-RA: parallel sparse index read aligner). The motivation in using SSAs is the ability to trade memory against time. It is possible to fine tune the space consumption of the index based on the available memory of the machine and the minimum length of the arriving pattern queries. Although SSAs have been studied before for exact matching of short reads, an elegant way of approximate matching capability was missing. We provide this by defining the rightmost mismatch criteria that prioritize the errors towards the end of the reads, where errors are more probable. Ψ-RA supports any number of mismatches in aligning reads. We give comparisons with some of the well-known short read aligners, and show that indexing a genome with SSA is a good alternative to the Burrows-Wheeler transform or seed-based solutions. CONCLUSIONS: Ψ-RA is expected to serve as a valuable tool in the alignment of short reads generated by the next generation high-throughput sequencing technology. Ψ-RA is very fast in exact matching and also supports rightmost approximate matching. The SSA structure that Ψ-RA is built on naturally incorporates the modern multicore architecture and thus further speed-up can be gained. All the information, including the source code of Ψ-RA, can be downloaded at: http://www.busillis.com/o_kulekci/PSIRA.zip.

Reconstructing One-Articulated Networks with Distance Matrices.

Given a distance matrix M that represents evolutionary distances between any two species, an edge-weighted phylogenetic network N is said to satisfy M if between any pair of species, there exists a path in N with a length equal to the corresponding entry in M. In this article, we consider a special class of networks called a one-articulated network, which is a proper superset of galled trees. We show that if the distance matrix M is derived from an ultrametric one-articulated network N (i.e., for any species X and Y, the entry [Formula: see text] is equal to the shortest distance between X and Y in N), we can re-construct a network that satisfies M in [Formula: see text] time, where n denotes the number of species; further, the reconstructed network is guaranteed to be the simplest, in a sense that the number of hybrid nodes is minimized. In addition, one may easily index a one-articulated network N with a minimum number of hybrid nodes in [Formula: see text] space, such that on any given phylogenetic tree T, we can determine whether T is contained in N (i.e., if a spanning subtree [Formula: see text] of N is a subdivision of T) in [Formula: see text] time.