Search

For every n ≥ 1 , generic models of ZFC will be presented for either of the following two sentences: 1. There exists a linear Σ n + 2 1 set not equal to the projection of any uniform planar Π n + 2 1 set. 2. There exists a linear Δ n + 2 1 set not equal to the projection of any uniform planar Π n + 1 1 set. Ensuing consistency and independence corollaries are discussed. [ABSTRACT FROM AUTHOR]

Simple Summary: The relationship between genomic characteristics and species traits is of paramount importance for biology. For genomic characteristics, we considered characteristics close to the rate of gene change in the process of evolution, including such extreme cases as pseudogenization and gene loss. This can be conceptualized as selection at the gene level. Amino acid substitutions in the positions that functionally determine protein domains were also considered. For species traits, we considered the maximal reported lifespan, the body weight of an adult animal, and the related longevity quotient. The first and second traits are also related, but only at the stochastic level; therefore, their behavior is a priori not similar. We proposed a novel technique that allows one to determine the relationship between any genomic characteristic and species traits. This technique is exemplified in the physiologically significant genes involved in regulating circadian rhythms, which change quite rapidly during evolution. Regardless of devising this technique, the study of the genes that are critical for circadian rhythms is of interest on its own. For instance, we thoroughly examined the paralogous genes Fbxl21 and Fbxl3, which are involved in the regulation of circadian rhythms. We found out that the above-mentioned characteristic of the Fbxl21 gene correlates with the maximal reported lifespan and body weight only in two superorders of placental mammals, Euarchontoglires (the clades Euarchonta, Lagomorpha, and Rodentia) and Afrotheria. On the contrary, such a correlation is not observed in other superorders, such as Laurasiatheria and Xenarthra. The presence or absence of the correlation is confirmed statistically with a very high accuracy. The rate of change in the Fbxl21 gene indicates, for example, the peculiarity of its evolution in apes. This article proposes a methodology for establishing a relationship between the change rate of a given gene (relative to a given taxon) together with the amino acid composition of the proteins encoded by this gene and the traits of the species containing this gene. The methodology is illustrated based on the mammalian genes responsible for regulating the circadian rhythms that underlie a number of human disorders, particularly those associated with aging. The methods used are statistical and bioinformatic ones. A systematic search for orthologues, pseudogenes, and gene losses was performed using our previously developed methods. It is demonstrated that the least conserved Fbxl21 gene in the Euarchontoglires superorder exhibits a statistically significant connection of genomic characteristics (the median of dN/dS for a gene relative to all the other orthologous genes of a taxon, as well as the preference or avoidance of certain amino acids in its protein) with species-specific lifespan and body weight. In contrast, no such connection is observed for Fbxl21 in the Laurasiatheria superorder. This study goes beyond the protein-coding genes, since the accumulation of amino acid substitutions in the course of evolution leads to pseudogenization and even gene loss, although the relationship between the genomic characteristics and the species traits is still preserved. The proposed methodology is illustrated using the examples of circadian rhythm genes and proteins in placental mammals, e.g., longevity is connected with the rate of Fbxl21 gene change, pseudogenization or gene loss, and specific amino acid substitutions (e.g., asparagine at the 19th position of the CRY-binding domain) in the protein encoded by this gene. [ABSTRACT FROM AUTHOR]

The mathematical side of applied problems in multiple subject areas (biology, pattern recognition, etc.) is reduced to the problem of discrete optimization in the following mathematical method. We were provided a network and graphs in its leaves, for which we needed to find a rearrangement of graphs by non-leaf nodes, in which the given functional reached its minimum. Such a problem, even in the simplest case, is NP-hard, which means unavoidable restrictions on the network, on graphs, or on the functional. In this publication, this problem is addressed in the case of all graphs being so-called "structures", meaning directed-loaded graphs consisting of paths and cycles, and the functional as the sum (over all edges in the network) of distances between structures at the endpoints of every edge. The distance itself is equal to the minimal length of sequence from the fixed list of operations, the composition of which transforms the structure at one endpoint of the edge into the structure at its other endpoint. The list of operations (and their costs) on such a graph is fixed. Under these conditions, the given discrete optimization problem is called the reconstruction problem. This paper presents novel algorithms for solving the reconstruction problem, along with full proofs of their low error and low polynomial complexity. For example, for the network, the problem is solved with a zero error algorithm that has a linear polynomial computational complexity; and for the tree the problem is solved using an algorithm with a multiplicative error of at most two, which has a second order polynomial computational complexity. [ABSTRACT FROM AUTHOR]

It was established by Jensen in 1970 that there is a generic extension L [ a ] of the constructible universe L by a non-constructible real a ∉ L , minimal over L , such that a is Δ 3 1 in L [ a ] . Our first main theorem generalizes Jensen's result by constructing, for each n ≥ 2 , a generic extension L [ a ] by a non-constructible real a ∉ L , still minimal over L , such that a is Δ n + 1 1 in L [ a ] but all Σ n 1 reals are constructible in L [ a ] . Jensen's forcing construction has found a number of applications in modern set theory. A problem was recently discussed as to whether Jensen's construction can be reproduced entirely by means of second-order Peano arithmetic PA 2 , or, equivalently, ZFC − (minus the power set axiom). The obstacle is that the proof of the key CCC property (whether by Jensen's original argument or the later proof using the diamond technique) essentially involves countable elementary submodels of L ω 2 , which is way beyond ZFC − . We demonstrate how to circumvent this difficulty by means of killing only definable antichains in the course of a Jensen-like transfinite construction of the forcing notion, and then use this modification to define a model with a minimal Δ n + 1 1 real as required as a class-forcing extension of a model of ZFC − plus V = L . [ABSTRACT FROM AUTHOR]

Background: It is generally accepted that most evolutionary transformations at the phenotype level are associated either with rearrangements of genomic regulatory elements, which control the activity of gene networks, or with changes in the amino acid contents of proteins. Recently, evidence has accumulated that significant evolutionary transformations could also be associated with the loss/emergence of whole genes. The targeted identification of such genes is a challenging problem for both bioinformatics and evo-devo research. Results: To solve this problem we propose the WINEGRET method, named after the first letters of the title. Its main idea is to search for genes that satisfy two requirements: first, the desired genes were lost/emerged at the same evolutionary stage at which the phenotypic trait of interest was lost/emerged, and second, the expression of these genes changes significantly during the development of the trait of interest in the model organism. To verify the first requirement, we do not use existing databases of orthologs, but rely purely on gene homology and local synteny by using some novel quickly computable conditions. Genes satisfying the second requirement are found by deep RNA sequencing. As a proof of principle, we used our method to find genes absent in extant amniotes (reptiles, birds, mammals) but present in anamniotes (fish and amphibians), in which these genes are involved in the regeneration of large body appendages. As a result, 57 genes were identified. For three of them, c-c motif chemokine 4, eotaxin-like, and a previously unknown gene called here sod4, essential roles for tail regeneration were demonstrated. Noteworthy, we established that the latter gene belongs to a novel family of Cu/Zn-superoxide dismutases lost by amniotes, SOD4. Conclusions: We present a method for targeted identification of genes whose loss/emergence in evolution could be associated with the loss/emergence of a phenotypic trait of interest. In a proof-of-principle study, we identified genes absent in amniotes that participate in body appendage regeneration in anamniotes. Our method provides a wide range of opportunities for studying the relationship between the loss/emergence of phenotypic traits and the loss/emergence of specific genes in evolution. [ABSTRACT FROM AUTHOR]

A model of set theory ZFC is defined in our recent research, in which, for a given n ≥ 3 , (A n) there exists a good lightface Δ n 1 well-ordering of the reals, but (B n) no well-orderings of the reals (not necessarily good) exist in the previous class Δ n − 1 1 . Therefore, the conjunction (A n) ∧ (B n) is consistent, modulo the consistency of ZFC itself. In this paper, we significantly clarify and strengthen this result. We prove the consistency of the conjunction (A n) ∧ (B n) for any given n ≥ 3 on the basis of the consistency of PA 2 , second-order Peano arithmetic, which is a much weaker assumption than the consistency of ZFC used in the earlier result. This is a new result that may lead to further progress in studies of the projective hierarchy. [ABSTRACT FROM AUTHOR]

We consider the problem of the existence of well-orderings of the reals, definable at a certain level of the projective hierarchy. This research is motivated by the modern development of descriptive set theory. Given n ≥ 3 , a finite support product of forcing notions similar to Jensen's minimal- Δ 3 1 -real forcing is applied to define a model of set theory in which there exists a good Δ n 1 well-ordering of the reals, but there are no Δ n − 1 1 well-orderings of the reals (not necessarily good). We conclude that the existence of a good well-ordering of the reals at a certain level n ≥ 3 of the projective hierarchy is strictly weaker than the existence of a such well-ordering at the previous level n − 1 . This is our first main result. We also demonstrate that this independence theorem can be obtained on the basis of the consistency of ZFC − (that is, a version of ZFC without the Power Set axiom) plus 'there exists the power set of ω ', which is a much weaker assumption than the consistency of ZFC usually assumed in such independence results obtained by the forcing method. This is our second main result. Further reduction to the consistency of second-order Peano arithmetic PA 2 is discussed. These are new results in such a generality (with n ≥ 3 arbitrary), and valuable improvements upon earlier results. We expect that these results will lead to further advances in descriptive set theory of projective classes. [ABSTRACT FROM AUTHOR]

According to Tzouvaras, a set is nontypical in the Russell sense if it belongs to a countable ordinal definable set. The class \mathbf {HNT} of all hereditarily nontypical sets satisfies all axioms of \mathbf {ZF} and the double inclusion \mathbf {HOD}\subseteq \mathbf {HNT}\subseteq \mathbf {V} holds. Several questions about the nature of such sets, recently proposed by Tzouvaras, are solved in this paper. In particular, a model of \mathbf {ZFC} is presented in which \mathbf {HOD}\subsetneqq \mathbf {HNT}\subsetneqq \mathbf {V}, and another model of \mathbf {ZFC} in which \mathbf {HNT} does not satisfy the axiom of choice. [ABSTRACT FROM AUTHOR]

The paper solves the problem of constructing an evolutionary tree and the evolution of structures along it. This problem has long been posed and extensively researched; it is formulated and discussed below. As a result, we construct an exact cubic-time algorithm which outputs a tree with the minimum cost of embedding into it and of embedding it into a given network (Theorem 1). We construct an algorithm that outputs a minimum embedding of a tree into a network, taking into account incomplete linear sorting; the algorithm depends linearly on the number of nodes in the network and is exact if the sorting cost is not less than the sum of the duplication cost and the loss cost (Theorem 3). We construct an exact approximately quadratic-time algorithm which, for arbitrary costs of SCJ operations, solves the problem of reconstruction of given structures on any two-star tree (Theorem 4). We construct an exact algorithm which reduced the problem of DCJ reconstruction of given structures on any star to a logarithmic-length sequence of SAT problems, each of them being of approximately quadratic size (Theorem 5). The theorems have rigorous and complete proofs of correctness and complexity of the algorithms, and are accompanied by numerical examples and numerous explanatory illustrations, including flowcharts. [ABSTRACT FROM AUTHOR]

We make use of generalized iterations of the Sacks forcing to define cardinal-preserving generic extensions of the constructible universe L in which the axioms of ZF hold and in addition either (1) the parameter-free countable axiom of choice AC ω * fails, or (2) AC ω * holds but the full countable axiom of choice AC ω fails in the domain of reals. In another generic extension of L, we define a set X ⊆ P (ω) , which is a model of the parameter-free part PA 2 * of the 2nd order Peano arithmetic PA 2 , in which CA (Σ 2 1) (Comprehension for Σ 2 1 formulas with parameters) holds, yet an instance of Comprehension CA for a more complex formula fails. Treating the iterated Sacks forcing as a class forcing over L ω 1 , we infer the following consistency results as corollaries. If the 2nd order Peano arithmetic PA 2 is formally consistent then so are the theories: (1) PA 2 + ¬ AC ω * , (2) PA 2 + AC ω * + ¬ AC ω , (3) PA 2 * + CA (Σ 2 1) + ¬ CA . [ABSTRACT FROM AUTHOR]

Alfred Tarski [J. Symbolic Logic 13 (1948), pp. 107–111] defined \mathbf {D}_{pm} to be the set of all sets of type p, type-theoretically definable by parameterfree formulas of type {\le m}, and asked whether it is true that \mathbf {D}_{1m}\in \mathbf {D}_{2m} for m\ge 1. Tarski noted that the negative solution is consistent because the axiom of constructibility \mathbf {V}=\mathbf {L} implies \mathbf {D}_{1m}\notin \mathbf {D}_{2m} for all m\ge 1, and he left the consistency of the positive solution as a major open problem. This was solved in our recent paper [Mathematics 8 (2020), pp. 1–36], where it is established that for any m\ge 1 there is a generic extension of \mathbf {L}, the constructible universe, in which it is true that \mathbf {D}_{1m}\in \mathbf {D}_{2m}. In continuation of this research, we prove here that Tarski's sentences \mathbf {D}_{1m}\in \mathbf {D}_{2m} are not only consistent, but also independent of each other, in the sense that for any set Y\subseteq \omega \smallsetminus \{0\} in \mathbf {L} there is a generic extension of \mathbf {L} in which it is true that \mathbf {D}_{1m}\in \mathbf {D}_{2m} holds for all m\in Y but fails for all m\ge 1, m\notin Y. This gives a full and conclusive solution of the Tarski problem. The other main result of this paper is the consistency of \mathbf {D}_{1}\in \mathbf {D}_{2} via another generic extension of \mathbf {L}, where \mathbf {D}_{p}=\bigcup _m\mathbf {D}_{pm}, the set of all sets of type p, type-theoretically definable by formulas of any type. Our methods are based on almost-disjoint forcing of Jensen and Solovay [Some applications of almost disjoint sets, North-Holland, Amsterdam, 1970, pp. 84–104]. [ABSTRACT FROM AUTHOR]

The problem of the existence of analytically definable well-orderings at a given level of the projective hierarchy is considered. This problem is important as a part of the general problem of the study of the projective hierarchy in the ongoing development of descriptive set theory. We make use of a finite support product of the Jensen-type forcing notions to define a model of set theory ZFC in which, for a given n > 2 , there exists a good Δ n 1 well-ordering of the reals but there are no such well-orderings in the class Δ n − 1 1 . Therefore the existence of a well-ordering of the reals at a certain level n > 2 of the projective hierarchy does not imply the existence of such a well-ordering at the previous level n − 1 . This is a new result in such a generality (with n > 2 arbitrary), and it may lead to further progress in studies of the projective hierarchy. [ABSTRACT FROM AUTHOR]

We make use of a finite support product of the Jensen-type forcing notions to define a model of the set theory ZFC in which, for a given n ≥ 3 , there exists a good lightface Δ n 1 well-ordering of the reals but there are no any (not necessarily good) well-orderings in the boldface class Δ n − 1 1. [ABSTRACT FROM AUTHOR]

The lengths of intergenic regions between neighboring genes that are convergent, divergent, or unidirectional were calculated for plastids of the rhodophytic branch and complete archaeal and bacterial genomes. Statistically significant linear relationships between any pair of the medians of these three length types have been revealed in each genomic group. Exponential relationships between the optimal growth temperature and each of the three medians have been revealed as well. The leading coefficients of the regression equations relating all pairs of the medians as well as temperature and any of the medians have the same sign and order of magnitude. The results obtained for plastids, archaea, and bacteria are also similar at the qualitative level. For instance, the medians are always low at high temperatures. At low temperatures, the medians tend to statistically significant greater values and scattering. The original model was used to test our hypothesis that the intergenic distances are optimized in particular to decrease the competition of RNA polymerases within the locus that results in transcribing shortened RNAs. Overall, this points to an effect of temperature for both remote and close genomes. [ABSTRACT FROM AUTHOR]

It is true in the Cohen, Solovay-random, and Sacks generic extensions that every ordinal-definable Borel set of reals has a Borel code in the ground model, and hence if non-empty, then has an element in the ground model. [ABSTRACT FROM AUTHOR]

Using a modification of the invariant Jensen forcing of [11] , we define a model of ZFC , in which, for a given n ≥ 3 , there exists a lightface Π n 1 -set of reals, which is a E 0 -equivalence class, hence a countable set, and which does not contain any OD element, while every non-empty countable Σ n 1 -set of reals is constructible, hence contains only OD reals. [ABSTRACT FROM AUTHOR]

It is true in the Cohen, Solovay-random, dominaning, and Sacks generic extension, that every countable ordinal-definable set of reals belongs to the ground universe. It is true in the Solovay collapse model that every non-empty OD countable set of sets of reals consists of OD elements. [ABSTRACT FROM AUTHOR]

Background: Chromosome structure is a very limited model of the genome including the information about its chromosomes such as their linear or circular organization, the order of genes on them, and the DNA strand encoding a gene. Gene lengths, nucleotide composition, and intergenic regions are ignored. Although highly incomplete, such structure can be used in many cases, e.g., to reconstruct phylogeny and evolutionary events, to identify gene synteny, regulatory elements and promoters (considering highly conserved elements), etc. Three problems are considered; all assume unequal gene content and the presence of gene paralogs. The distance problem is to determine the minimum number of operations required to transform one chromosome structure into another and the corresponding transformation itself including the identification of paralogs in two structures. We use the DCJ model which is one of the most studied combinatorial rearrangement models. Double-, sesqui-, and single-operations as well as deletion and insertion of a chromosome region are considered in the model; the single ones comprise cut and join. In the reconstruction problem, a phylogenetic tree with chromosome structures in the leaves is given. It is necessary to assign the structures to inner nodes of the tree to minimize the sum of distances between terminal structures of each edge and to identify the mutual paralogs in a fairly large set of structures. A linear algorithm is known for the distance problem without paralogs, while the presence of paralogs makes it NP-hard. If paralogs are allowed but the insertion and deletion operations are missing (and special constraints are imposed), the reduction of the distance problem to integer linear programming is known. Apparently, the reconstruction problem is NP-hard even in the absence of paralogs. The problem of contigs is to find the optimal arrangements for each given set of contigs, which also includes the mutual identification of paralogs. Results: We proved that these problems can be reduced to integer linear programming formulations, which allows an algorithm to redefine the problems to implement a very special case of the integer linear programming tool. The results were tested on synthetic and biological samples. Conclusions: Three well-known problems were reduced to a very special case of integer linear programming, which is a new method of their solutions. Integer linear programming is clearly among the main computational methods and, as generally accepted, is fast on average; in particular, computation systems specifically targeted at it are available. The challenges are to reduce the size of the corresponding integer linear programming formulations and to incorporate a more detailed biological concept in our model of the reconstruction. [ABSTRACT FROM AUTHOR]

We make use of a finite support product of the Jensen minimal Π 2 1 singleton forcing to define a model in which Π 2 1 uniformization fails for a set with countable cross-sections. We also define appropriate submodels of the same model in which separation fails for Π 3 1 . [ABSTRACT FROM AUTHOR]

Background: One of the main aims of phylogenomics is the reconstruction of objects defined in the leaves along the whole phylogenetic tree to minimize the specified functional, which may also include the phylogenetic tree generation. Such objects can include nucleotide and amino acid sequences, chromosomal structures, etc. The structures can have any set of linear and circular chromosomes, variable gene composition and include any number of paralogs, as well as any weights of individual evolutionary operations to transform a chromosome structure. Many heuristic algorithms were proposed for this purpose, but there are just a few exact algorithms with low (linear, cubic or similar) polynomial computational complexity among them to our knowledge. The algorithms naturally start from the calculation of both the distance between two structures and the shortest sequence of operations transforming one structure into another. Such calculation per se is an NP-hard problem. Results: A general model of chromosomal structure rearrangements is considered. Exact algorithms with almost linear or cubic polynomial complexities have been developed to solve the problems for the case of any chromosomal structure but with certain limitations on operation weights. The computer programs are tested on biological data for the problem of mitochondrial or plastid chromosomal structure reconstruction. To our knowledge, no computer programs are available for this model. Conclusions: Exactness of the proposed algorithms and such low polynomial complexities were proved. The reconstructed evolutionary trees of mitochondrial and plastid chromosomal structures as well as the ancestral states of the structures appear to be reasonable. [ABSTRACT FROM AUTHOR]

A generic extension $${\mathbf{L}[x]}$$ by a real x is defined, in which the $${\mathsf{E}_0}$$ -class of x is a lightface $${{\it \Pi}^1_2}$$ (hence, ordinal-definable) set containing no ordinal-definable reals. [ABSTRACT FROM AUTHOR]

Highlights: [•] We predict the involvement of poorly characterized proteins in sulfur metabolism. [•] The cysteine-dependent regulation was predicted for many genes. [•] The regulon contains subunits of the transporters of sulfur-containing compounds. [•] The regulated genes might have been horizontally transferred. [•] The results considerably extend studies of classic and Rho-dependent attenuations. [Copyright &y& Elsevier]

We prove several dichotomy theorems which extend some known results on σ-bounded and σ-compact pointsets. In particular we show that, given a finite number of \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Delta ^{1}_{1}$\end{document} equivalence relations \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathrel {\mathsf {F}}_1,\dots ,\mathrel {\mathsf {F}}_n$\end{document}, any \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{1}_{1}$\end{document} set A of the Baire space either is covered by compact \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Delta ^{1}_{1}$\end{document} sets and lightface \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Delta ^{1}_{1}$\end{document} equivalence classes of the relations \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathrel {\mathsf {F}}_i$\end{document}, or A contains a superperfect subset which is pairwise \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathrel {\mathsf {F}}_i$\end{document}-inequivalent for all i = 1, ..., n. Further generalizations to \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{1}_{2}$\end{document} sets A are obtained. [ABSTRACT FROM AUTHOR]

This study considers transcription regulation of plastid genes involved in sulfate transport in the parasites of invertebrate (Helicosporidium sp.) and other species of the Viridiplantae. A one-box conserved motif with the consensus TAAWATGATT is found near promoters upstream the cysT and cysA genes in many species. In certain cases, the motif is repeated two or three times. [ABSTRACT FROM AUTHOR]

Abstract: In the early years of set theory, Du Bois Reymond introduced a vague notion of infinitary pantachie meant to symbolize an infinity bigger than the infinity of real numbers. Hausdorff reformulated this concept rigorously as a maximal chain (a linearly ordered subset) in a partially ordered set of certain type, for instance, the set under eventual domination. Hausdorff proved the existence of a pantachy in any partially ordered set, using the axiom of choice AC. We show in this note that the pantachy existence theorem fails in the absense of AC, and moreover, even if AC is assumed, hence pantachies do exist, one may not be able to come up with an individual, effectively defined example of a pantachy. [Copyright &y& Elsevier]

Background: A long recognized problem is the inference of the supertree S that amalgamates a given set {Gj} of trees Gj, with leaves in each Gj being assigned homologous elements. We ground on an approach to find the tree S by minimizing the total cost of mappings αj of individual gene trees Gj into S. Traditionally, this cost is defined basically as a sum of duplications and gaps in each αj. The classical problem is to minimize the total cost, where S runs over the set of all trees that contain an exhaustive non-redundant set of species from all input Gj. Results: We suggest a reformulation of the classical NP-hard problem of building a supertree in terms of the global minimization of the same cost functional but only over species trees S that consist of clades belonging to a fixed set P (e.g., an exhaustive set of clades in all Gj). We developed a deterministic solving algorithm with a low degree polynomial (typically cubic) time complexity with respect to the size of input data. We define an extensive set of elementary evolutionary events and suggest an original definition of mapping β of tree G into tree S. We introduce the cost functional c(G, S, f ) and define the mapping β as the global minimum of this functional with respect to the variable f, in which sense it is a generalization of classical mapping α. We suggest a reformulation of the classical NP-hard mapping (reconciliation) problem by introducing time slices into the species tree S and present a cubic time solving algorithm to compute the mapping β. We introduce two novel definitions of the evolutionary scenario based on mapping β or a random process of gene evolution along a species tree. Conclusions: Developed algorithms are mathematically proved, which justifies the following statements. The supertree building algorithm finds exactly the global minimum of the total cost if only gene duplications and losses are allowed and the given sets of gene trees satisfies a certain condition. The mapping algorithm finds exactly the minimal mapping β, the minimal total cost and the evolutionary scenario as a minimum over all possible distributions of elementary evolutionary events along the edges of tree S. The algorithms and their effective software implementations provide useful tools in many biological studies. They facilitate processing of voluminous tree data in acceptable time still largely avoiding heuristics. Performance of the tools is tested with artificial and prokaryotic tree data. [ABSTRACT FROM AUTHOR]

Background: In previous work, we introduced a concept, a mathematical model and its computer realization that describe the interaction between bacterial and phage type RNA polymerases, protein factors, DNA and RNA secondary structures during transcription, including transcription initiation and termination. The model accurately reproduces changes of gene transcription level observed in polymerase sigma-subunit knockout and heat shock experiments in plant plastids. The corresponding computer program and a user guide are available at http://lab6. iitp.ru/en/rivals. Here we apply the model to the analysis of transcription and (partially) translation processes in the mitochondria of frog, rat and human. Notably, mitochondria possess only phage-type polymerases. We consider the entire mitochondrial genome so that our model allows RNA polymerases to complete more than one circle on the DNA strand. Results: Our model of RNA polymerase interaction during transcription initiation and elongation accurately reproduces experimental data obtained for plastids. Moreover, it also reproduces evidence on bulk RNA concentrations and RNA half-lives in the mitochondria of frog, human with or without the MELAS mutation, and rat with normal (euthyroid) or hyposecretion of thyroid hormone (hypothyroid). The transcription characteristics predicted by the model include: (i) the fraction of polymerases terminating at a protein-dependent terminator in both directions (the terminator polarization), (ii) the binding intensities of the regulatory protein factor (mTERF) with the termination site and, (iii) the transcription initiation intensities (initiation frequencies) of all promoters in all five conditions (frog, healthy human, human with MELAS syndrome, healthy rat, and hypothyroid rat with aberrant mtDNA methylation). Using the model, absolute levels of all gene transcription can be inferred from an arbitrary array of the three transcription characteristics, whereas, for selected genes only relative RNA concentrations have been experimentally determined. Conversely, these characteristics and absolute transcription levels can be obtained using relative RNA concentrations and RNA half-lives known from various experimental studies. In this case, the "inverse problem" is solved with multi-objective optimization. Conclusions: In this study, we demonstrate that our model accurately reproduces all relevant experimental data available for plant plastids, as well as the mitochondria of chordates. Using experimental data, the model is applied to estimate binding intensities of phage-type RNA polymerases to their promoters as well as predicting terminator characteristics, including polarization. In addition, one can predict characteristics of phage-type RNA polymerases and the transcription process that are difficult to measure directly, e.g., the association between the promoter's nucleotide composition and the intensity of polymerase binding. To illustrate the application of our model in functional predictions, we propose a possible mechanism for MELAS syndrome development in human involving a decrease of Phe-tRNA, Val-tRNA and rRNA concentrations in the cell. In addition, we describe how changes in methylation patterns of the mTERF binding site and three promoters in hypothyroid rat correlate with changes in intensities of the mTERF binding and transcription initiations. Finally, we introduce an auxiliary model to describe the interaction between polysomal mRNA and ribonucleases. [ABSTRACT FROM AUTHOR]

Background: Modeling of a complex biological process can explain the results of experimental studies and help predict its characteristics. Among such processes is transcription in the presence of competing RNA polymerases. This process involves RNA polymerases collision followed by transcription termination. Results: A mathematical and computer simulation model is developed to describe the competition of RNA polymerases during genes transcription on complementary DNA strands. E.g., in the barley Hordeum vulgare the polymerase competition occurs in the locus containing plastome genes psbA, rpl23, rpl2 and four bacterial type promoters. In heat shock experiments on isolated chloroplasts, a twofold decrease of psbA transcripts and even larger increase of rpl23-rpl2 transcripts were observed, which is well reproduced in the model. The model predictions are in good agreement with virtually all relevant experimental data (knockout, heat shock, chromatogram data, etc.). The model allows to hypothesize a mechanism of cell response to knockout and heat shock, as well as a mechanism of gene expression regulation in presence of RNA polymerase competition. The model is implemented for multiprocessor platforms with MPI and supported on Linux and MS Windows. The source code written in C++ is available under the GNU General Public License from the laboratory website. A userfriendly GUI version is also provided at http://lab6.iitp.ru/en/rivals. Conclusions: The developed model is in good agreement with virtually all relevant experimental data. The model can be applied to estimate intensities of binding of the holoenzyme and phage type RNA polymerase to their promoters using data on gene transcription levels, as well as to predict characteristics of RNA polymerases and the transcription process that are difficult to measure directly, e.g., the intensity (frequency) of holoenzyme binding to the promoter in correlation to its nucleotide composition and the type of σ-subunit, the amount of transcription initiation aborts, etc. The model can be used to make functional predictions, e.g., heat shock response in isolated chloroplasts and changes of gene transcription levels under knockout of different σ-subunits or RNA polymerases or due to gene expression regulation. Reviewers: This article was reviewed by Dr. Anthony Almudevar, Dr. Aniko Szabo, Dr. Yuri Wolf (nominated by Dr. Peter Olofsson) and Prof. Marek Kimmel. [ABSTRACT FROM AUTHOR]

We demonstrate the scarcity of conserved bacterial-type promoters in plastids of Streptophyta and report widely conserved promoters only for genes psaA, psbA, psbB, psbE, rbcL. Among the reasonable explanations are: evolutionary changes of sigma subunit paralogs and phage-type RNA polymerases possibly entailing the loss of corresponding nuclear genes, de novo emergence of the promoters, their loss together with plastome genes; functional substitution of the promoter boxes by transcription activation factor binding sites. Reviewers: This article was reviewed by Dr. Arcady Mushegian, and by Dr. Alexander Bolshoy and Dr. Yuri Wolf (both nominated by Dr. Purificación López-García). [ABSTRACT FROM AUTHOR]

Abstract: Following a research line suggested by Ilijas Farah, we prove that for any abelian Polish σ-compact group there exists an Radon–Nikodym ideal, that is, an ideal together with a Borel -approximate homomorphism which is not -approximable by a continuous true homomorphism . [Copyright &y& Elsevier]

RNAmodel web server was recently established at the IITP RAS to implement our previously proposed model of the classic attenuation regulation of gene expression in bacteria. This new model is based on the concept of resonant-like interaction between RNA polymerase and hairpins of RNA secondary structure formed during transcription. Our modeling relies on standard Monte Carlo procedures and covers all essential stages of the process, including initiation and elongation of transcription and translation; the deceleration of ribosome on regulatory codons, which depends on the concentration of charged amino acyl-tRNA; the polymerase shifting delay caused by secondary structure folded into the mRNA segment between ribosome and polymerase; and, ultimately, either transcription terminating prematurely or polymerase reaching a region of structural genes (antitermination). By means of Monte Carlo simulation we build a function p(c) which expresses the probability of termination (i.e., an enzyme activity) vs. the concentration of charged amino acyl-tRNA or of amino acid itself, measured in actual or relative units. [ABSTRACT FROM AUTHOR]

A model is proposed primarily for the classical RNA attenuation regulation of gene expression through premature transcription termination. The model is based on the concept of the RNA secondary structure macrostate within the regulatory region between the ribosome and RNA-polymerase, on hypothetical equation describing deceleration of RNA-polymerase by a macrostate and on views of transcription and translation initiation and elongation, under different values of the four basic model parameters which were varied. A special effort was made to select adequate model parameters. We first discuss kinetics of RNA folding and define the concept of the macrostate as a specific parentheses structure used to construct a conventional set of hairpins. The originally developed software that realizes the proposed model offers functionality to fully model RNA secondary folding kinetics. Its performance is compared to that of a public server described in Ref. 1. We then describe the delay in RNA-polymerase shifting to the next base or its premature termination caused by an RNA secondary structure or, herefrom, a macrostate. In this description, essential concepts are the basic and excited states of the polymerase first introduced in Ref. 2: the polymerase shifting to the next base can occur only in the basic state, and its detachment from DNA strand — only in excited state. As to the authors' knowledge, such a model incorporating the above-mentioned attenuation characteristics is not published elsewhere. The model was implemented in an application with command line interface for running in batch mode in Windows and Linux environments, as well as a public web server.3 The model was tested with a conventional Monte Carlo procedure. In these simulations, the estimate of correlation between the premature transcription termination probability p and concentration c of charged amino acyl-tRNA was obtained as function p(c) for many regulatory regions in many bacterial genomes, as well as for local mutations in these regions. [ABSTRACT FROM AUTHOR]

The paper provides a short description of the originally developed algorithm for searching of the conservative protein–RNA binding sites. The algorithm is applied to analyze chloroplast genes. The candidate protein–RNA binding sites were detected upstream of atpF, petB, clpP, psaA, psbA, and psbB genes in many chloroplasts of algae and plants. We suggest that some of these sites are involved in suppressing translation until splicing is completed. [ABSTRACT FROM AUTHOR]

A new approach for comparative analysis of multiple trees reconstructed for representative protein families is proposed. This approach is based on the hypothesis of gene duplication, gene loss and horizontal gene transfer and makes use of stochastic methods and optimization. We present a species tree of 40 prokaryotic organisms obtained by our algorithm on the basis of 132 clusters of orthologous groups of proteins (COGs) from the GenBank of the National Center for Biotechnology Information (USA). We also present a computer technology intended to determine horizontally transferred genes. Some application results of the technology, based on comparative analysis of protein and species trees, are given. [ABSTRACT FROM AUTHOR]

We describe an algorithm (IRSA) for identification of common regulatory signals in samples of unaligned DNA sequences. The algorithm was tested on randomly generated sequences of fixed length with implanted signal of length 15 with 4 mutations, and on natural upstream regions of bacterial genes regulated by PurR, ArgR and CRP. Then it was applied to upstream regions of orthologous genes from Escherichia coli and related genomes. Some new palindromic binding and direct repeats signals were identified. Finally we present a parallel version suitable for computers supporting the MPI protocol. This implementation is not strictly bounded by the number of available processors. The computation speed linearly depends on the number of processors. [ABSTRACT FROM AUTHOR]

The notion of ordinal definability and the related notions of ordinal definable sets (class OD) and hereditarily ordinal definable sets (class HOD) belong to the key concepts of modern set theory. Recent studies have discovered more general types of sets, still based on the notion of ordinal definability, but in a more blurry way. In particular, Tzouvaras has recently introduced the notion of sets nontypical in the Russell sense, so that a set x is nontypical if it belongs to a countable ordinal definable set. Tzouvaras demonstrated that the class HNT of all hereditarily nontypical sets satisfies all axioms of ZF and satisfies HOD ⊆ HNT . In view of this, Tzouvaras proposed a problem—to find out whether the class HNT can be separated from HOD by the strict inclusion HOD ⫋ HNT , and whether it can also be separated from the universe V of all sets by the strict inclusion HNT ⫋ V , in suitable set theoretic models. Solving this problem, a generic extension L [ a , x ] of the Gödel-constructible universe L , by two reals a , x , is presented in this paper, in which the relation L = HOD ⫋ L [ a ] = HNT ⫋ L [ a , x ] = V is fulfilled, so that HNT is a model of ZFC strictly between HOD and the universe. Our result proves that the class HNT is really a new rich class of sets, which does not necessarily coincide with either the well-known class HOD or the whole universe V. This opens new possibilities in the ongoing study of the consistency and independence problems in modern set theory. [ABSTRACT FROM AUTHOR]

For any weighted directed path-cycle graphs, a and b (referred to as structures), and any equal costs of operations (intermergings and duplication), we obtain an algorithm which, by successively applying these operations to a, outputs b if the first structure contains no paralogs (i.e., edges with a repeated name) and the second has no more than two paralogs for each edge. In finding the shortest sequence of operations to be applied to pass from a to b, the algorithm has a multiplicative error of at most 13/9 + ε, where ε is any strictly positive number, and its runtime is of the order of n O (ε − 2.6) , where n is the size of the input pair of graphs. In the case of no paralogs, equal sets of names in the structures, and equal operation costs, we have considered the following conditions on the transformation of a into b: all structures in them are from one cycle; all structures are from one path; all structures are from paths. For each of the conditions, we have obtained an exact (i.e., zero-error) quadratic time algorithm for finding the shortest transformation of a into b. For another list of operations (join and cut of a vertex, and deletion and insertion of an edge) over structures and for arbitrary costs of these operations, we have obtained an algorithm for the extension of structures specified at the leaves of a tree onto its interior vertices. The algorithm is exact if the tree is a star—in this case, structures in the leaves may even have unequal sets of names or paralogs. The runtime of the algorithm is of the order of nΧ + n2log(n), where n is the number of names in the leaves, and Χ is an easily computable characteristic of the structures in the leaves. In the general case, a cubic time algorithm finds a locally minimal solution. [ABSTRACT FROM AUTHOR]

A finite support product of ω 1 clones of Jensen's minimal Π 2 1 singleton forcing is used to define a model in which any non-empty analytically definable set of reals contains an analytically definable real (the full basis theorem), but there is no analytically definable wellordering of the reals. [ABSTRACT FROM AUTHOR]

In this paper we prove that for any m ≥ 1 there exists a generic extension of L , the constructible universe, in which it is true that the set of all constructible reals (here subsets of ω) is equal to the set D 1 m of all reals definable by a parameter free type-theoretic formula with types bounded by m, and hence the Tarski 'definability of definable' sentence D 1 m ∈ D 2 m (even in the form D 1 m ∈ D 21 ) holds for this particular m. This solves an old problem of Alfred Tarski (1948). Our methods, based on the almost-disjoint forcing of Jensen and Solovay, are significant modifications and further development of the methods presented in our two previous papers in this Journal. [ABSTRACT FROM AUTHOR]

We propose a novel linear time algorithm which, given any directed weighted graphs a and b with vertex degrees 1 or 2, constructs a sequence of operations transforming a into b. The total cost of operations in this sequence is minimal among all possible ones or differs from the minimum by an additive constant that depends only on operation costs but not on the graphs themselves; this difference is small as compared to the operation costs and is explicitly computed. We assume that the double cut and join operations have identical costs, and costs of the deletion and insertion operations are arbitrary strictly positive rational numbers. [ABSTRACT FROM AUTHOR]

In this paper, we prove the following. If n ≥ 3 , then there is a generic extension of L , the constructible universe, in which it is true that the set P (ω) ∩ L of all constructible reals (here—subsets of ω) is equal to the set P (ω) ∩ Δ n 1 of all (lightface) Δ n 1 reals. The result was announced long ago by Leo Harrington, but its proof has never been published. Our methods are based on almost-disjoint forcing. To obtain a generic extension as required, we make use of a forcing notion of the form Q = C ℂ × ∏ ν Q ν in L , where C adds a generic collapse surjection b from ω onto P (ω) ∩ L , whereas each Q ν , ν < ω 2 L , is an almost-disjoint forcing notion in the ω 1 -version, that adjoins a subset S ν of ω 1 L . The forcing notions involved are independent in the sense that no Q ν -generic object can be added by the product of C and all Q ξ , ξ ≠ ν . This allows the definition of each constructible real by a Σ n 1 formula in a suitably constructed subextension of the Q -generic extension. The subextension is generated by the surjection b, sets S ω · k + j with j ∈ b (k) , and sets S ξ with ξ ≥ ω · ω . A special character of the construction of forcing notions Q ν is L , which depends on a given n ≥ 3 , obscures things with definability in the subextension enough for vice versa any Δ n 1 real to be constructible; here the method of hidden invariance is applied. A discussion of possible further applications is added in the conclusive section. [ABSTRACT FROM AUTHOR]

Models of set theory are defined, in which nonconstructible reals first appear on a given level of the projective hierarchy. Our main results are as follows. Suppose that n ≥ 2 . Then: 1. If it holds in the constructible universe L that a ⊆ ω and a ∉ Σ n 1 ∪ Π n 1 , then there is a generic extension of L in which a ∈ Δ n + 1 1 but still a ∉ Σ n 1 ∪ Π n 1 , and moreover, any set x ⊆ ω , x ∈ Σ n 1 , is constructible and Σ n 1 in L. 2. There exists a generic extension L in which it is true that there is a nonconstructible Δ n + 1 1 set a ⊆ ω , but all Σ n 1 sets x ⊆ ω are constructible and even Σ n 1 in L , and in addition, V = L [ a ] in the extension. 3. There exists an generic extension of L in which there is a nonconstructible Σ n + 1 1 set a ⊆ ω , but all Δ n + 1 1 sets x ⊆ ω are constructible and Δ n + 1 1 in L. Thus, nonconstructible reals (here subsets of ω) can first appear at a given lightface projective class strictly higher than Σ 2 1 , in an appropriate generic extension of L. The lower limit Σ 2 1 is motivated by the Shoenfield absoluteness theorem, which implies that all Σ 2 1 sets a ⊆ ω are constructible. Our methods are based on almost-disjoint forcing. We add a sufficient number of generic reals to L , which are very similar at a given projective level n but discernible at the next level n + 1 . [ABSTRACT FROM AUTHOR]

A generic extension [ABSTRACT FROM AUTHOR]

This study considers transcription regulation of plastid genes involved in sulfate transport in the parasites of invertebrate (Helicosporidium sp.) and other species of the Viridiplantae. A one-box conserved motif with the consensus TAAWATGATT is found near promoters upstream the cysT and cysA genes in many species. In certain cases, the motif is repeated two or three times. [ABSTRACT FROM AUTHOR]

Parasitic life-strategies in the phylum Nematoda (roundworms) are remarkably diverse and intricate in terms of evolution and taxonomy. By analysing novel rDNA data obtained on rare host-associated groups with unusual biology, we reveal paraphyly of the last major taxon with uncertain higher-rank classification that united solely parasitic nematodes (Marimermithida) to show that primarily marine parasitism only emerged independently and repeatedly in a few free-living lineages. We report secondary seaward ingression of land-based parasites (Mermithida) via invading hosts in the subtidal zone to illustrate the host-borne scenario of oceanic fish and mammal colonization by primarily terrestrial parasites (Spiruria). We also present the first molecular data on marine nematodes from unicellular hosts (foraminiferan protozoans) to demonstrate the independent origins of exploitative nematode associations at a microscopic scale. We argue that, in contrast with primarily intestinal associations arising from saprotrophy and commensalism, non-intestinal host capture (colonization of host body cavity or internal organs) is likely to be a primary route of transition to truly exploitative parasitism in roundworms. Predispositions to host capture in nematode morphology, ecology and life cycles imply its evolution as part of innate pre-adaptations to crossing environmental boundaries to enable multiple successful transitions to parasitism in the phylum history. [ABSTRACT FROM AUTHOR]

A novel algorithm and original software were used to cluster all proteins encoded in plastids of 72 species of the rhodophytic branch. The results are publicly available at http://lab6.iitp.ru/ppc/redline72/ in a database that allows fast identification of clusters (protein families) both by a fragment of an amino acid sequence and by a phylogenetic profile of a protein. No such integral clustering with the corresponding functions can be found in the public domain. The putative regulons of the transcription factors Ycf28 and Ycf29 encoded in the plastids were identified using the clustering and the database. A regulation of translation initiation was proposed for the ycf24 gene in plastids of certain red algae and apicomplexans as well as a regulation of a putative gene in apicoplasts of Babesia spp. and Theileria parva. The conserved regulation of the ycf24 gene expression and specificity alternation of the transcription factor Ycf28 were shown in the plastids. A phylogenetic tree of plastids was generated for the rhodophytic branch. The hypothesis of the origin of apicoplasts from the common ancestor of all apicomplexans from plastids of red algae was confirmed. [ABSTRACT FROM AUTHOR]