Fast exact algorithms for the closest string and substring problems with application to the planted (L, d)-motif model

We present two parameterized algorithms for the closest string problem. The first runs in O(nL + nd · 17.97d) time for DNA strings and in O(nL + nd · 61.86d) time for protein strings, where n is the number of input strings, L is the length of each input string, and d is the given upper bound on the number of mismatches between the center string and each input string. The second runs in O(nL + nd · 13.92d) time for DNA strings and in O(nL + nd · 47.21d) time for protein strings. We then extend the first algorithm to a new parameterized algorithm for the closest substring problem that runs in O((n - 1)m2(L + d · 17.97d · m[log2(d+1)])) time for DNA strings and in O((n - 1)m2(L + d · 61.86d · m[log2(d+1)])) time for protein strings, where n is the number of input strings, L is the length of the center substring, L - 1 + m is the maximum length of a single input string, and d is the given upper bound on the number of mismatches between the center substring and at least one substring of each input string. All the algorithms significantly improve the previous bests. To verify experimentally the theoretical improvements in the time complexity, we implement our algorithm in C and apply the resulting program to the planted (L, d)-motif problem proposed by Pevzner and Sze in 2000. We compare our program with the previously best exact program for the problem, namely PMSPrune (designed by Davila et al. in 2007). Our experimental data show that our program runs faster for practical cases and also for several challenging cases. Our algorithm uses less memory too.     

Hierarchical coding of letter strings in the ventral stream: dissecting the inner organization of the visual word-form system

Visual word recognition has been proposed to rely on a hierarchy of increasingly complex neuronal detectors, from individual letters to bigrams and morphemes. We used fMRI to test whether such a hierarchy is present in the left occipitotemporal cortex, at the site of the visual word-form area, and with an anterior-to-posterior progression. We exposed adult readers to (1) false-font strings; (2) strings of infrequent letters; (3) strings of frequent letters but rare bigrams; (4) strings with frequent bigrams but rare quadrigrams; (5) strings with frequent quadrigrams; (6) real words. A gradient of selectivity was observed through the entire span of the occipitotemporal cortex, with activation becoming more selective for higher-level stimuli toward the anterior fusiform region. A similar gradient was also seen in left inferior frontoinsular cortex. Those gradients were asymmetrical in favor of the left hemisphere. We conclude that the left occipitotemporal visual word-form area, far from being a homogeneous structure, presents a high degree of functional and spatial hierarchical organization which must result from a tuning process during reading acquisition.     

Large pore gels to separate mega protein complexes larger than 10 MDa by blue native electrophoresis: Isolation of putative respiratory strings or patches

Here, we expand the application of blue native electrophoresis to the separation of mega protein complexes larger than 10 MDa by introducing novel large pore acrylamide gels. We tailored the bis‐acrylamide cross‐linker amounts relative to the acrylamide monomer to enlarge the pore size of acrylamide gels and to obtain elastic and sufficiently stable gels. The novel gel types were then used to search for suprastructures of mitochondrial respiratory supercomplexes, the hypothetical respiratory strings, or patches. We identified 4–8 MDa assemblies that contain respiratory complexes I, III, and IV and most likely represent dimers, trimers, and tetramers of respiratory supercomplexes. We also isolated multimeric respiratory supercomplexes with apparent masses of 35–45 MDa, the presumed core pieces of respiratory strings or patches. Electron microscopic investigations will be required to clarify whether the isolated assemblies of complexes are ordered and specific, as predicted for respiratory strings and patches in the mitochondrial membrane.     

Assembly and Activation of Alternative Complement Components on Endothelial Cell-Anchored Ultra-Large Von Willebrand Factor Links Complement and Hemostasis-Thrombosis

Background

Vascular endothelial cells (ECs) express and release protein components of the complement pathways, as well as secreting and anchoring ultra-large von Willebrand factor (ULVWF) multimers in long string-like structures that initiate platelet adhesion during hemostasis and thrombosis. The alternative complement pathway (AP) is an important non-antibody-requiring host defense system. Thrombotic microangiopathies can be associated with defective regulation of the AP (atypical hemolytic-uremic syndrome) or with inadequate cleavage by ADAMTS-13 of ULVWF multimeric strings secreted by/anchored to ECs (thrombotic thrombocytopenic purpura). Our goal was to determine if EC-anchored ULVWF strings caused the assembly and activation of AP components, thereby linking two essential defense mechanisms.

Methodology/Principal Findings

We quantified gene expression of these complement components in cultured human umbilical vein endothelial cells (HUVECs) by real-time PCR: C3 and C5; complement factor (CF) B, CFD, CFP, CFH and CFI of the AP; and C4 of the classical and lectin (but not alternative) complement pathways. We used fluorescent microscopy, monospecific antibodies against complement components, fluorescent secondary antibodies, and the analysis of >150 images to quantify the attachment of HUVEC-released complement proteins to ULVWF strings secreted by, and anchored to, the HUVECs (under conditions of ADAMTS-13 inhibition). We found that HUVEC-released C4 did not attach to ULVWF strings, ruling out activation of the classical and lectin pathways by the strings. In contrast, C3, FB, FD, FP and C5, FH and FI attached to ULVWF strings in quantitative patterns consistent with assembly of the AP components into active complexes. This was verified when non-functional FB blocked the formation of AP C3 convertase complexes (C3bBb) on ULVWF strings.

Conclusions/Significance

AP components are assembled and activated on EC-secreted/anchored ULVWF multimeric strings. Our findings provide one possible molecular mechanism for clinical linkage between different types of thrombotic and complement-mediated disorders.     

Entropy and complexity of finite sequences as fluctuating quantities.

The paper is devoted to the analysis of digitized sequences of real numbers and discrete strings, by means of the concepts of entropy and complexity. Special attention is paid to the random character of these quantities and their fluctuation spectrum. As applications, we discuss neural spike-trains and DNA sequences. We consider a given sequence as one realization of finite length of certain random process. The other members of the ensemble are defined by appropriate surrogate sequences and surrogate processes. We show that n-gram entropies and the context-free grammatical complexity have to be considered as fluctuating quantities and study the corresponding distributions. Different complexity measures reveal different aspects of a sequence. Finally, we show that the diversity of the entropy (that takes small values for pseudorandom strings) and the context-free grammatical complexity (which takes large values for pseudorandom strings) give, nonetheless, consistent results by comparison of the ranking of sample sequences taken from molecular biology, neuroscience, and artificial control sequences.     

Self-replicating sequences of binary numbers. Foundations I: General

We propose the general framework of a new algorithm, derived from the interactions of chains of RNA, which is capable of self-organization. It considers sequences of binary numbers (strings) and their interaction with each other. Analogous to RNA systems, a folding of sequences is introduced to generate alternative two-dimensional forms of the binary sequences. The two-dimensional forms of strings can naturally interact with one-dimensional forms and generate new sequences. These new sequences compete with the original strings due to selection pressure. Populations of initially random strings develop in a stochastic reaction system, following the reaction channels between string types. In particular, replicating and self-replicating string types can be observed in such systems.Dedicated to Professor Hermann Haken on the occasion of this 65th birthday     

Assignment of paternity groups without access to parental genotypes: multiple mating and developmental plasticity in squid

We present a novel approach to investigating sibling relationships and reconstructing parental genotypes from a progeny array. The Bayesian method we have employed is flexible and may be applicable to a variety of situations in addition to the one presented here. While mutation rates and breeding population allele frequencies can be taken into account, the model requires relatively few loci and makes few assumptions. Paternity of 270 veined squid (Loligo forbesi) hatchlings from three egg strings collected from one location was assigned using five microsatellite loci. Paternal and maternal genotypes reconstructed for each of the three strings were identical, strongly indicating that a single female produced the strings that were fertilized by the same four males. The proportion of eggs fertilized was not equal between males in all three strings, with male 1 siring most offspring (up to 68% in string 1), through to male 4 siring the least (as low as 2.4% in string 1). Although temperature had a profound effect on incubation time, paternity did not affect this trait at 12 degrees C or 8 degrees C.     

Remodeling Tissue Interfaces and the Thermodynamics of Zipping during Dorsal Closure in Drosophila

Dorsal closure during Drosophila embryogenesis is an important model system for investigating the biomechanics of morphogenesis. During closure, two flanks of lateral epidermis (with actomyosin-rich purse strings near each leading edge) close an eye-shaped opening that is filled with amnioserosa. At each canthus (corner of the eye) a zipping process remodels the tissue interfaces between the leading edges of the lateral epidermis and the amnioserosa. We investigated zipping dynamics and found that apposing leading edge cells come together at their apical ends and then square off basally to form a lateral junction. Meanwhile, the purse strings act as contractile elastic rods bent toward the embryo interior near each canthus. We propose that a canthus-localized force contributes to both bending the ends of the purse strings and the formation of lateral junctions. We developed a thermodynamic model for zipping based on three-dimensional remodeling of the tissue interfaces and the reaction dynamics of adhesion molecules in junctions and elsewhere, which we applied to zipping during unperturbed wild-type closure and to laser or genetically perturbed closure. We identified two processes that can contribute to the zipping mechanism, consistent with experiments, distinguished by whether amnioserosa dynamics do or do not augment canthus adhesion dynamics.     

Altered flower/fruit clusters of the kitul palm used as roosts by the short-nosed fruit bat, Cynopterus sphinx (Chiroptera: Pteropodidae)

The short-nosed fruit bat (Cynopterus sphinx) creates bell-shaped cavities in flower/fruit clusters of the kitul palm (Caryota urens) by chewing and severing flower and fruit strings. These cavities (stem tents) in which the bats roost are usually about one metre deep and 30 cm in diameter. We observed groups of bats roosting in fully-formed stem tents during the daytime, and the construction and subsequent occupancy of newly formed tent cavities. Stem tents are similar in principle to leaf tents except, instead of being formed when bats chew veins and the surrounding tissues of leaves, stem tents are formed in C. urens when bats completely cut several of the central flower/fruit strings. Flower/fruit strings are mostly severed when they are in an immature stage, at times when they are thin and widely spaced. Once these strings thicken and become heavily-laden with mature fruits, bats cannot penetrate the cluster to sever them. Our observations suggest that a single male enters an immature flower or fruit cluster either from below or the sides and severs the central strings along the peduncle. In early phases of stem-tent construction, C. sphinx severs flower/fruit strings at a rate of about one or two per day, and cluster alteration may continue upwards to two months. Only one immature flower/fruit cluster on a C. urens tree is available for alteration by bats at any given time. That this bat does not roost in the fruit/flower cluster during the day, when a tent is under construction, and the accumulation of chewed flower and fruit strings beneath such a cluster in the morning, suggests that tent construction by C. sphinx is a night-time activity.     

Eccentricity bias as an organizing principle for human high-order object areas

We have recently proposed a center-periphery organization based on resolution needs, in which objects engaging in recognition processes requiring central-vision (e.g., face-related) are associated with center-biased representations, while objects requiring large-scale feature integration (e.g., buildings) are associated with periphery-biased representations. Here we tested this hypothesis by comparing the center-periphery organization with activations to five object categories: faces, buildings, tools, letter strings, and words. We found that faces, letter strings, and words were mapped preferentially within the center-biased representation. Faces showed a hemispheric lateralization opposite to that of letter strings and words. In contrast, buildings were mapped mainly to the periphery-biased representation, while tools activated both central and peripheral representations. The results are compatible with the notion that center-periphery organization allows the optimal allocation of cortical magnification to the specific requirements of various recognition processes.     

Finite-state models in the alignment of macromolecules

Summary Minimum message length encoding is a technique of inductive inference with theoretical and practical advantages. It allows the posterior odds-ratio of two theories or hypotheses to be calculated. Here it is applied to problems of aligning or relating two strings, in particular two biological macromolecules. We compare the r-theory, that the strings are related, with the null-theory, that they are not related. If they are related, the probabilities of the various alignments can be calculated. This is done for one-, three-, and five-state models of relation or mutation. These correspond to linear and piecewise linear cost functions on runs of insertions and deletions. We describe how to estimate parameters of a model. The validity of a model is itself an hypothesis and can be objectively tested. This is done on real DNA strings and on artificial data. The tests on artificial data indicate limits on what can be inferred in various situations. The tests on real DNA support either the three- or five-state models over the one-state model. Finally, a fast, approximate minimum message length string comparison algorithm is described.Offprint requests to: L. Allison     

Speeding up whole-genome alignment by indexing frequency vectors

MOTIVATION: Many biological applications require the comparison of large genome strings. Current techniques suffer from high computational and I/O costs. RESULTS: We propose an efficient technique for local alignment of large genome strings. A space-efficient index is computed for one string, and the second string is compared with this index in order to prune substring pairs that do not contain similar regions. The remaining substring pairs are handed to a hash-table-based tool, such as BLAST, for alignment. A dynamic strategy is employed to optimize the number of disk seeks needed to access the hash table. Additionally, our technique provides the user with a coarse-grained visualization of the similarity pattern, quickly and before the actual search. The experimental results show that our technique aligns genome strings up to two orders of magnitude faster than BLAST. Our technique can be used to accelerate other search tools as well. AVAILABILITY: A web-based demo can be found at http://bioserver.cs.ucsb.edu/. Source code is available from the authors on request.     

Distribution of the number of matches between nucleotide sequences

When two strings of symbols are aligned it is important to know whether the observed number of matches is better than that expected between two independent sequences with the same frequency of symbols. When strings are of different lengths, nulls need to be inserted in order to align the sequences. One approach is to use simple approximations of sampling for replacement. We describe an algorithm for exactly determining the frequencies of given numbers of matches, sampling without replacement. This does not lead to a simple closed form expression. However we show examples where sampling with, or without, replacement give very similar results and the simple approach may be adequate for all but the smallest cases.     

Finding subtle motifs by branching from sample strings

Many motif finding algorithms apply local search techniques to a set of seeds. For example, GibbsDNA (Lawrence et al. 1993, Science, 262, 208-214) applies Gibbs sampling to random seeds, and MEME (Bailey and Elkan, 1994, Proceedings of the Second International Conference on Intelligent Systems for Molecular Biology (ISMB-94), 28-36) applies the EM algorithm to selected sample strings, i.e. substrings of the sample. In the case of subtle motifs, recent benchmarking efforts show that both random seeds and selected sample strings may never get close to the globally optimal motif. We propose a new approach which searches motif space by branching from sample strings, and implement this idea in both pattern-based and profile-based settings. Our PatternBranching and ProfileBranching algorithms achieve favorable results relative to other motif finding algorithms. Availability: http://www-cse.ucsd.edu/groups/bioinformatics/software.html     

Self-replicating sequences of binary numbers. Foundations II: Strings of length N=4

We study an algorithm which allows sequences of binary numbers (strings) to interact with each other. The simplest system of this kind with a population of 4-bit sequences is considered here. Previously proposed folding methods are used to generate alternative two-dimensional forms of the binary sequences. The interaction of two-dimensional and one-dimensional forms of strings is simulated in a serial computer. The reaction network for the N = 4 system is established. Development of string populations initially generated randomly is observed. Nonlinear rate equations are proposed which provide a model for this simplest system.Dedicated to Professor Hermann Haken on the occasion of his 65th Birthday     

Glocal alignment: finding rearrangements during alignment

MOTIVATION: To compare entire genomes from different species, biologists increasingly need alignment methods that are efficient enough to handle long sequences, and accurate enough to correctly align the conserved biological features between distant species. The two main classes of pairwise alignments are global alignment, where one string is transformed into the other, and local alignment, where all locations of similarity between the two strings are returned. Global alignments are less prone to demonstrating false homology as each letter of one sequence is constrained to being aligned to only one letter of the other. Local alignments, on the other hand, can cope with rearrangements between non-syntenic, orthologous sequences by identifying similar regions in sequences; this, however, comes at the expense of a higher false positive rate due to the inability of local aligners to take into account overall conservation maps. RESULTS: In this paper we introduce the notion of glocal alignment, a combination of global and local methods, where one creates a map that transforms one sequence into the other while allowing for rearrangement events. We present Shuffle-LAGAN, a glocal alignment algorithm that is based on the CHAOS local alignment algorithm and the LAGAN global aligner, and is able to align long genomic sequences. To test Shuffle-LAGAN we split the mouse genome into BAC-sized pieces, and aligned these pieces to the human genome. We demonstrate that Shuffle-LAGAN compares favorably in terms of sensitivity and specificity with standard local and global aligners. From the alignments we conclude that about 9% of human/mouse homology may be attributed to small rearrangements, 63% of which are duplications.     

PRODUCTIVITY AND DIVERSITY IN A CROSS‐FEEDING POPULATION OF ARTIFICIAL ORGANISMS

Cross‐feeding interactions are a common feature of many microbial systems, such as colonies of Escherichia coli grown on a single limiting resource, and microbial consortia cooperatively degrading complex compounds. We have studied this phenomenon from an abstract point of view by considering artificial organisms that metabolize binary strings from a shared environment. The organisms are represented as simple cellular automaton rules and the analog of energy in the system is an approximation of the Shannon entropy of the binary strings. Only organisms that increase the entropy of the transformed strings are allowed to replicate. This system exhibits a large degree of species diversity, which increases when the flow of binary strings into the system is reduced. Investigating the relation between ecosystem productivity and diversity we find that diversity is negatively correlated with biomass production and energy uptake, while it correlates positively with energy‐uptake efficiency. By performing invasion experiments, we show that the source of diversity is negative frequency‐dependent selection acting among the different species, and that some of these interactions are intransitive, another mechanism known to promote diversity.     

The posterior probability distribution of alignments and its application to parameter estimation of evolutionary trees and to optimization of multiple alignments

How to sample alignments from their posterior probability distribution given two strings is shown. This is extended to sampling alignments of more than two strings. The result is first applied to the estimation of the edges of a given evolutionary tree over several strings. Second, when used in conjunction with simulated annealing, it gives a stochastic search method for an optimal multiple alignment.Correspondence to: L. Allison     

"Simulated molecular evolution" or computer-generated artifacts?

1. The authors define a function with value 1 for the positive examples and 0 for the negative ones. They fit a continuous function but do not deal at all with the error margin of the fit, which is almost as large as the function values they compute. 2. The term "quality" for the value of the fitted function gives the impression that some biological significance is associated with values of the fitted function strictly between 0 and 1, but there is no justification for this kind of interpretation and finding the point where the fit achieves its maximum does not make sense. 3. By neglecting the error margin the authors try to optimize the fitted function using differences in the second, third, fourth, and even fifth decimal place which have no statistical significance. 4. Even if such a fit could profit from more data points, the authors should first prove that the region of interest has some kind of smoothness, that is, that a continuous fit makes any sense at all. 5. "Simulated molecular evolution" is a misnomer. We are dealing here with random search. Since the margin of error is so large, the fitted function does not provide statistically significant information about the points in search space where strings with cleavage sites could be found. This implies that the method is a highly unreliable stochastic search in the space of strings, even if the neural network is capable of learning some simple correlations. 6. Classical statistical methods are for these kind of problems with so few data points clearly superior to the neural networks used as a "black box" by the authors, which in the way they are structured provide a model with an error margin as large as the numbers being computed.7. And finally, even if someone would provide us with a function which separates strings with cleavage sites from strings without them perfectly, so-called simulated molecular evolution would not be better than random selection.Since a perfect fit would only produce exactly ones or zeros,starting a search in a region of space where all strings in the neighborhood get the value zero would not provide any kind of directional information for new iterations. We would just skip from one point to the other in a typical random walk manner.     

Live imaging of prions reveals nascent PrPSc in cell-surface,raft-associated amyloid strings and webs

Mammalian prions refold host glycosylphosphatidylinositol-anchored PrP^C into β-sheet–rich PrP^Sc. PrP^Sc is rapidly truncated into a C-terminal PrP27-30 core that is stable for days in endolysosomes. The nature of cell-associated prions, their attachment to membranes and rafts, and their subcellular locations are poorly understood; live prion visualization has not previously been achieved. A key obstacle has been the inaccessibility of PrP27-30 epitopes. We overcame this hurdle by focusing on nascent full-length PrP^Sc rather than on its truncated PrP27-30 product. We show that N-terminal PrP^Sc epitopes are exposed in their physiological context and visualize, for the first time, PrP^Sc in living cells. PrP^Sc resides for hours in unexpected cell-surface, slow moving strings and webs, sheltered from endocytosis. Prion strings observed by light and scanning electron microscopy were thin, micrometer-long structures. They were firmly cell associated, resisted phosphatidylinositol-specific phospholipase C, aligned with raft markers, fluoresced with thioflavin, and were rapidly abolished by anti-prion glycans. Prion strings and webs are the first demonstration of membrane-anchored PrP^Sc amyloids.