Genome Rearrangement Analysis : Cut and Join Genome Rearrangements and Gene Cluster Preserving Approaches.

Genome rearrangements are mutations that change the gene content of a genome or the arrangement of the genes on a genome. Several years of research on genome rearrangements have established different algorithmic approaches for solving some fundamental problems in comparative genomics based on gene order information. This review summarizes the literature on genome rearrangement analysis along two lines of research.

DeGeCI 1.1: a web platform for gene annotation of mitochondrial genomes.

Summary: DeGeCI is a command line tool that generates fully automated gene predictions from mitochondrial nucleotide sequences by using a reference database of annotated mitogenomes which is represented as a de Bruijn graph. The input genome is mapped to this graph, creating a subgraph, which is then post-processed by a clustering routine. Version 1.

Fully automated annotation of mitochondrial genomes using a cluster-based approach with de Bruijn graphs.

A wide range of scientific fields, such as forensics, anthropology, medicine, and molecular evolution, benefits from the analysis of mitogenomic data. With the development of new sequencing technologies, the amount of mitochondrial sequence data to be analyzed has increased exponentially over the last few years. The accurate annotation of mitochondrial DNA is a prerequisite for any mitogenomic comparative analysis.

Detecting gene breakpoints in noisy genome sequences using position-annotated colored de-Bruijn graphs.

Background: Identifying the locations of gene breakpoints between species of different taxonomic groups can provide useful insights into the underlying evolutionary processes. Given the exact locations of their genes, the breakpoints can be computed without much effort. However, often, existing gene annotations are erroneous, or only nucleotide sequences are available.

Iterated Local Search and Other Algorithms for Buffered Two-Machine Permutation Flow Shops with Constant Processing Times on One Machine.

The two-machine permutation flow shop scheduling problem with buffer is studied for the special case that all processing times on one of the two machines are equal to a constant c. This case is interesting because it occurs in various applications, for example, when one machine is a packing machine or when materials have to be transported. Different types of buffers and buffer usage are considered.

Evolutionary Dynamic Multiobjective Optimization via Learning From Historical Search Process.

Dynamic multiobjective optimization problems are challenging due to their fast convergence and diversity maintenance requirements. Prediction-based evolutionary algorithms currently gain much attention for meeting these requirements. However, it is not always the case that an elaborate predictor is suitable for different problems and the quality of historical solutions is sufficient to support prediction, which limits the availability of prediction-based methods over various problems.

Individual differences in honey bee behavior enabled by plasticity in brain gene regulatory networks.

Understanding the regulatory architecture of phenotypic variation is a fundamental goal in biology, but connections between gene regulatory network (GRN) activity and individual differences in behavior are poorly understood. We characterized the molecular basis of behavioral plasticity in queenless honey bee () colonies, where individuals engage in both reproductive and non-reproductive behaviors. Using high-throughput behavioral tracking, we discovered these colonies contain a continuum of phenotypes, with some individuals specialized for either egg-laying or foraging and 'generalists' that perform both.

Re-assessing the diversity of negative strand RNA viruses in insects.

The spectrum of viruses in insects is important for subjects as diverse as public health, veterinary medicine, food production, and biodiversity conservation. The traditional interest in vector-borne diseases of humans and livestock has drawn the attention of virus studies to hematophagous insect species. However, these represent only a tiny fraction of the broad diversity of Hexapoda, the most speciose group of animals.

Improved annotation of protein-coding genes boundaries in metazoan mitochondrial genomes.

With the rapid increase of sequenced metazoan mitochondrial genomes, a detailed manual annotation is becoming more and more infeasible. While it is easy to identify the approximate location of protein-coding genes within mitogenomes, the peculiar processing of mitochondrial transcripts, however, makes the determination of precise gene boundaries a surprisingly difficult problem. We have analyzed the properties of annotated start and stop codon positions in detail, and use the inferred patterns to devise a new method for predicting gene boundaries in de novo annotations.

Sorting Signed Permutations by Inverse Tandem Duplication Random Losses.

Gene order evolution of unichromosomal genomes, for example mitochondrial genomes, has been modelled mostly by four major types of genome rearrangements: inversions, transpositions, inverse transpositions, and tandem duplication random losses. Generalizing models that include all those rearrangements while admitting computational tractability are rare. In this paper, we study such a rearrangement model, namely the inverse tandem duplication random loss (iTDRL) model, where an iTDRL duplicates and inverts a continuous segment of a gene order followed by the random loss of one of the redundant copies of each gene.

A strict upper bound for the partition distance and the cluster distance of phylogenetic trees for each fixed pair of topological trees.

For each given pair of (rooted or unrooted) topological trees with the same number of leaves a strict upper bound is shown for the tree partition distance (also called symmetric difference metric and Robinson-Foulds distance)-in case of unrooted trees-and for the cluster distance (also called Robinson-Foulds distance)-in case of rooted trees-of corresponding phylogenetic trees. In particular, it is shown that there exist assignments of labels (e.g.

An Exact Algorithm for Sorting by Weighted Preserving Genome Rearrangements.

The preserving Genome Sorting Problem (pGSP) asks for a shortest sequence of rearrangement operations that transforms a given gene order into another given gene order by using rearrangement operations that preserve common intervals, i.e., groups of genes that form an interval in both given gene orders.

EqualTDRL: illustrating equivalent tandem duplication random loss rearrangements.

Background: To study the differences between two unichromosomal circular genomes, e.g., mitochondrial genomes, under the tandem duplication random loss (TDRL) rearrangement it is important to consider the whole set of potential TDRL rearrangement events that could have taken place.

Automated monitoring of behavior reveals bursty interaction patterns and rapid spreading dynamics in honeybee social networks.

Social networks mediate the spread of information and disease. The dynamics of spreading depends, among other factors, on the distribution of times between successive contacts in the network. Heavy-tailed (bursty) time distributions are characteristic of human communication networks, including face-to-face contacts and electronic communication via mobile phone calls, email, and internet communities.

Genome Rearrangement Analysis: Cut and Join Genome Rearrangements and Gene Cluster Preserving Approaches.

Genome rearrangements are mutations that change the gene content of a genome or the arrangement of the genes on a genome. Several years of research on genome rearrangements have established different algorithmic approaches for solving some fundamental problems in comparative genomics based on gene order information. This review summarizes the literature on genome rearrangement analysis along two lines of research.

Genome Rearrangement with ILP.

The weighted Genome Sorting Problem (wGSP) is to find a minimum-weight sequence of rearrangement operations that transforms a given gene order into another given gene order using rearrangement operations that are associated with a predefined weight. This paper presents a polynomial sized Integer Linear Program -called GeRe-ILP- for solving the wGSP for the following three types of rearrangement operations: inversion , transposition, and inverse transposition. GeRe-ILP uses variables and constraints for gene orders of length .

Combinatorics of Tandem Duplication Random Loss Mutations on Circular Genomes.

The tandem duplication random loss operation (TDRL) is an important genome rearrangement operation in metazoan mitochondrial genomes. A TDRL consists of a duplication of a contiguous set of genes in tandem followed by a random loss of one copy of each duplicated gene. This paper presents an analysis of the combinatorics of TDRLs on circular genomes, e.

Cophylogenetic Reconciliation with ILP.

In this paper, we present an integer linear programming (ILP) approach, called CoRe-ILP, for finding an optimal time consistent cophylogenetic host-parasite reconciliation under the cophylogenetic event model with the events cospeciation, duplication, sorting, host switch, and failure to diverge. Instead of assuming event costs, a simplified model is used, maximizing primarily for cospeciations and secondarily minimizing host switching events. Duplications, sortings, and failure to diverge events are not explicitly scored.

Towards a comprehensive picture of alloacceptor tRNA remolding in metazoan mitochondrial genomes.

Remolding of tRNAs is a well-documented process in mitochondrial genomes that changes the identity of a tRNA. It involves a duplication of a tRNA gene, a mutation that changes the anticodon and the loss of the ancestral tRNA gene. The net effect is a functional tRNA that is more closely related to tRNAs of a different alloacceptor family than to tRNAs with the same anticodon in related species.

A Branch-and-Bound Approach for Tautomer Enumeration.

Knowledge about tautomer forms of a structure is important since, e.g., a property prediction for a molecule can yield to different results which depend on the individual tautomer.

Phylogenomics with paralogs.

Phylogenomics heavily relies on well-curated sequence data sets that comprise, for each gene, exclusively 1:1 orthologos. Paralogs are treated as a dangerous nuisance that has to be detected and removed. We show here that this severe restriction of the data sets is not necessary.

Local similarity search to find gene indicators in mitochondrial genomes.

Given a set of nucleotide sequences we consider the problem of identifying conserved substrings occurring in homologous genes in a large number of sequences. The problem is solved by identifying certain nodes in a suffix tree containing all substrings occurring in the given nucleotide sequences. Due to the large size of the targeted data set, our approach employs a truncated version of suffix trees.

Challenges in RNA virus bioinformatics.

Motivation: Computer-assisted studies of structure, function and evolution of viruses remains a neglected area of research. The attention of bioinformaticians to this interesting and challenging field is far from commensurate with its medical and biotechnological importance. It is telling that out of >200 talks held at ISMB 2013, the largest international bioinformatics conference, only one presentation explicitly dealt with viruses.

An empirically based simulation of group foraging in the harvesting ant, Messor pergandei.

We present an empirically based group model of foraging interactions in Messor pergandei, the Sonoran desert harvesting ant. M. pergandei colonies send out daily foraging columns consisting of tens of thousands of individual ants.