A major goal of natural computing is to design biomolecules, such as nucleic acid sequences, that can be used to perform computations. We design sequences of nucleic acids that are "guaranteed" to have long folding pathways relative to their length. This particular sequences with high probability follow low-barrier folding pathways that visit a large number of distinct structures. Long folding pathways are interesting, because they demonstrate that natural computing can potentially support long and complex computations. Formally, we provide the first scalable designs of molecules whose low-barrier folding pathways, with respect to a simple, stacked pair energy model, grow superlinearly with the molecule length, but for which all significantly shorter alternative folding pathways have an energy barrier that is [Formula: see text] times that of the low-barrier pathway for any [Formula: see text] and a sufficiently long sequence.

Genome mapping algorithms aim at computing an ordering of a set of genomic markers based on local ordering information such as adjacencies and intervals of markers. In most genome mapping models, markers are assumed to occur uniquely in the resulting map. We introduce algorithmic questions that consider repeats, i.e., markers that can have several occurrences in the resulting map. We show that, provided with an upper bound on the copy number of repeated markers and with intervals that span full repeat copies, called repeat spanning intervals, the problem of deciding if a set of adjacencies and repeat spanning intervals admits a genome representation is tractable if the target genome can contain linear and/or circular chromosomal fragments. We also show that extracting a maximum cardinality or weight subset of repeat spanning intervals given a set of adjacencies that admits a genome realization is NP-hard but fixed-parameter tractable in the maximum copy number and the number of adjacent repeats, and tractable if intervals contain a single repeated marker.

We show that in the hierarchical tile assembly model, if there is a producible assembly that overlaps a nontrivial translation of itself consistently (i.e., the pattern of tile types in the overlap region is identical in both translations), then arbitrarily large assemblies are producible. The significance of this result is that tile systems intended to controllably produce finite structures must avoid pattern repetition in their producible assemblies that would lead to such overlap. This answers an open question of Chen and Doty (SODA 2012), who showed that so-called "partial-order" systems producing a unique finite assembly and avoiding such overlaps must require time linear in the assembly diameter. An application of our main result is that any system producing a unique finite assembly is automatically guaranteed to avoid such overlaps, simplifying the hypothesis of Chen and Doty's main theorem.

Chemical reaction networks (CRNs) and DNA strand displacement systems (DSDs) are widely-studied and useful models of molecular programming. However, in order for some DSDs in the literature to behave in an expected manner, the initial number of copies of some reagents is required to be fixed. In this paper we show that, when multiple copies of all initial molecules are present, general types of CRNs and DSDs fail to work correctly if the length of the shortest sequence of reactions needed to produce any given molecule exceeds a threshold that grows polynomially with attributes of the system.

BACKGROUND: Recovering the structure of ancestral genomes can be formalized in terms of properties of binary matrices such as the Consecutive-Ones Property (C1P). The Linearization Problem asks to extract, from a given binary matrix, a maximum weight subset of rows that satisfies such a property. This problem is in general intractable, and in particular if the ancestral genome is expected to contain only linear chromosomes or a unique circular chromosome. In the present work, we consider a relaxation of this problem, which allows ancestral genomes that can contain several chromosomes, each either linear or circular. RESULT: We show that, when restricted to binary matrices of degree two, which correspond to adjacencies, the genomic characters used in most ancestral genome reconstruction methods, this relaxed version of the Linearization Problem is polynomially solvable using a reduction to a matching problem. This result holds in the more general case where columns have bounded multiplicity, which models possibly duplicated ancestral genes. We also prove that for matrices with rows of degrees 2 and 3, without multiplicity and without weights on the rows, the problem is NP-complete, thus tracing sharp tractability boundaries. CONCLUSION: As it happened for the breakpoint median problem, also used in ancestral genome reconstruction, relaxing the definition of a genome turns an intractable problem into a tractable one. The relaxation is adapted to some biological contexts, such as bacterial genomes with several replicons, possibly partially assembled. Algorithms can also be used as heuristics for hard variants. More generally, this work opens a way to better understand linearization results for ancestral genome structure inference.

The primary objective of this work was to identify those human phosphorylation sites (phosphosites) that are highly conserved in other species as this may reveal functionally important phosphosites. We wondered whether human phosphosites (e.g. tyrosine, serine or threonine) that are known to be activatory upon phosphorylation, are commonly replaced by a glutamic or aspartic acid residues in other species. This type of alteration might mimic constitutive phosphorylation of cognate proteins in other species, which would indicate that phosphorylation of these sites in humans may confer functionality. To investigate this, we developed an algorithm to identify ortholog proteins in different species for each given human phospho-protein and also predict phosphosites in every extracted ortholog cognate protein. The results demonstrate that relatively few human phosphosites are highly conserved; for instance from about 90,000 human phosphosites, about 75% of these were conserved in mammals, but less than 16% were detected in most model organisms. These extremely well conserved phosphosites did not display any increased preponderance for acidic amino acid substitutions. However, we observed that the most conserved functional phosphosites occurred on threonine phosphosites that were found in protein kinases and these were 8-times more likely to be stimulatory than inhibitory.

In this paper we propose a new algorithm to predict the phosphorylation site specificities of 478 human protein kinases based on the primary structures of the catalytic domains of these enzymes. Existing methods deduce the specificity of a protein kinase through the alignment of the amino acid sequences of phospho-sites targeted by the kinase to generate a consensus sequence or they use machine learning models for recognition. However, for most protein kinases few if any substrates have been experimentally identified by protein sequencing and mass spectrometry. In this work, we used mutual information from a training set of over 200 protein kinases consensus phospho-site sequences and predicted amino acid interactions between kinases and their substrate phospho-sites to generate position-specific scoring matrices (PSSM). The results demonstrate that using our algorithm, knowledge of the primary amino acid sequence of the catalytic domain of these kinases is sufficient to predict their phosphorylation sites specificities and their PSSM matrices.

We introduce two variants of proper colorings with imposed partial ordering on the set of colors. One variant shows very close connections to some fundamental problems in graph theory, e.g., directed graph homomorphism and list colorings. We study the border between tractability and intractability for both variants.

We consider what is the amount of subwords of a word needed to completely determine the word. More precisely, we study the maximal length such that all words of this length can be uniquely determined by its subwords of a fixed length. The set of subwords of a fixed length is called a spectrum. Four types of spectrums are analyzed: sparse, factor, sparse with multiplicity and factor with multiplicity. We also study the equivalence between the proper spectrum (subwords of a fixed length) and full spectrum (subwords at most of a fixed length) for each case. In all cases except sparse with multiplicity we give a precise answer. The results about factors and about the equivalence between the proper and full spectrums are new. TUCS Research Group