A Barrier for Further Approximating Sorting by Transpositions.

The transposition distance problem is a classical problem in genome rearrangements, which seeks to determine the minimum number of transpositions needed to transform a linear chromosome into another represented by the permutations π and σ, respectively. This article focuses on the equivalent problem of sorting by transpositions (SBT), where σ is the identity permutation ι. Specifically, we investigate palisades, a family of permutations that are "hard" to sort, as they require numerous transpositions above the celebrated lower bound devised by Bafna and Pevzner. By determining the transposition distance of palisades, we were able to provide the exact transposition diameter for 3-permutations (TD3), a special subset of the symmetric group Sn, essential for the study of approximate solutions for SBT using the simplification technique. The exact value for TD3 has remained unknown since Elias and Hartman showed an upper bound for it. Another consequence of determining the transposition distance of palisades is that, using as lower bound the one by Bafna and Pevzner, it is impossible to guarantee approximation ratios lower than 1.375 when approximating SBT. This finding has significant implications for the study of SBT, as this problem has been the subject of intense research efforts for the past 25 years.

Live neighbor-joining.

BACKGROUND: In phylogenetic reconstruction the result is a tree where all taxa are leaves and internal nodes are hypothetical ancestors. In a live phylogeny, both ancestral and living taxa may coexist, leading to a tree where internal nodes may be living taxa. The well-known Neighbor-Joining heuristic is largely used for phylogenetic reconstruction. RESULTS: We present Live Neighbor-Joining, a heuristic for building a live phylogeny. We have investigated Live Neighbor-Joining on datasets of viral genomes, a plausible scenario for its application, which allowed the construction of alternative hypothesis for the relationships among virus that embrace both ancestral and descending taxa. We also applied Live Neighbor-Joining on a set of bacterial genomes and to sets of images and texts. Non-biological data may be better explored visually when their relationship in terms of content similarity is represented by means of a phylogeny. CONCLUSION: Our experiments have shown interesting alternative phylogenetic hypothesis for RNA virus genomes, bacterial genomes and alternative relationships among images and texts, illustrating a wide range of scenarios where Live Neighbor-Joining may be used.

Guarana (Paullinia cupana var. sorbilis), an anciently consumed stimulant from the Amazon rain forest: the seeded-fruit transcriptome.

Guarana (Paullinia cupana var. sorbilis) is a plant native to the central Amazon basin. Roasted seed extracts have been used as medicinal beverages since pre-Colombian times, due to their reputation as stimulants, aphrodisiacs, tonics, as well as protectors of the gastrointestinal tract. Guarana plants are commercially cultivated exclusively in Brazil to supply the national carbonated soft-drink industry and natural product stores around the world. In this report, we describe and discuss the annotation of 15,387 ESTs from guarana seeded-fruits, highlighting sequences from the flavonoid and purine alkaloid pathways, and those related to biotic stress avoidance. This is the largest set of sequences registered for the Sapindaceae family.