Abstract. A [Formula: see text] -uniform tight cycle is a [Formula: see text]-graph with a cyclic ordering of its vertices such that its edges are precisely the sets of [Formula: see text] consecutive vertices in that ordering. A [Formula: see text] -uniform tight path is a [Formula: see text]-graph obtained by deleting a vertex from a [Formula: see text]-uniform tight cycle. We prove that the Ramsey number for the 4-uniform tight cycle on [Formula: see text] vertices is [Formula: see text]. This is asymptotically tight. This result also implies that the Ramsey number for the 4-uniform tight path on [Formula: see text] vertices is [Formula: see text].

Let $\vec{T}_k$ be the transitive tournament on $k$ vertices. We show that every oriented graph on $n=4m$ vertices with minimum total degree $(11/12+o(1))n$ can be partitioned into vertex disjoint $\vec{T}_4$'s, and this bound is asymptotically tight. We also improve the best known bound on the minimum total degree for partitioning oriented graphs into vertex disjoint $\vec{T}_k$'s.

A branch vertex in a tree is a vertex of degree at least three. We prove that, for all $s\geq 1$, every connected graph on $n$ vertices with minimum degree at least $(\frac{1}{s+3}+o(1))n$ contains a spanning tree having at most $s$ branch vertices. Asymptotically, this is best possible and solves a problem of Flandrin, Kaiser, Kuz̆el, Li, and Ryjác̆ek, which was originally motivated by an optimization problem in the design of optical networks.

Let $r\ge 3$. Given an $r$-graph $H$, the minimum codegree $\delta_{r-1}(H)$ is the largest integer $t$ such that every $(r-1)$-subset of $V(H)$ is contained in at least $t$ edges of $H$. Given an $r$-graph $F$, the codegree Turán density $\gamma(F)$ is the smallest $\gamma >0$ such that every $r$-graph on $n$ vertices with $\delta_{r-1}(H)\ge (\gamma + o(1))n$ contains $F$ as a subhypergraph. Using results on the independence number of hypergraphs, we show that there are constants $c_1, c_2>0$ depending only on $r$ such that $1 - c_2 \tfrac{\ln t}{t^{r-1}} \le \gamma(K_t^r) \le 1 - c_1 \tfrac{\ln t}{t^{r-1}},$ where $K_t^r$ is the complete $r$-graph on $t$ vertices. This gives the best general bounds for $\gamma(K_t^r)$.

Let $G$ be an edge-colored graph. The minimum color degree $\delta^c(G)$ of $G$ is the largest integer $k$ such that for every vertex $v$, there are at least $k$ distinct colors on edges incident to $v$. We say that $G$ is properly colored if no two adjacent edges have the same color. In this paper, we show that every edge-colored graph $G$ with $\delta^c(G) \ge 2|G|/3$ contains a properly colored $2$-factor. Furthermore, we show that for any $\varepsilon > 0 $ there exists an integer $n_0$ such that every edge-colored graph $G$ with $|G| = n \ge n_0$ and $\delta^c(G) \ge ( 2/3 + \varepsilon ) n $ contains a properly colored cycle of length $\ell$ for every $3 \le \ell \le n$. This result is best possible in the sense that the statement is false for $\delta^c(G) < 2n/3$.

Let $H_n$ be a $k$-graph on $n$ vertices. For $0 \le \ell \ell >1$, the set of $\pi_{\ell}^k(\mathcal{F})$ is dense in the interval $[0,1)$. Hence, there is no “jump” for $\ell$-degree Turán density when $k>\ell >1$. We also give a lower bound on $\pi_{\ell}^k(\mathcal{F})$ in terms of an ordinary Turán density.

BACKGROUND: Since membrane protein structures are challenging to crystallize, computational approaches are essential for elucidating the sequence-to-structure relationships. Structural modeling of membrane proteins requires a multidimensional approach, and one critical geometric parameter is the rotational angle of transmembrane helices. Rotational angles of transmembrane helices are characterized by their folded structures and could be inferred by the hydrophobic moment; however, the folding mechanism of membrane proteins is not yet fully understood. The rotational angle of a transmembrane helix is related to the exposed surface of a transmembrane helix, since lipid exposure gives the degree of accessibility of each residue in lipid environment. To the best of our knowledge, there have been few advances in investigating whether an environment descriptor of lipid exposure could infer a geometric parameter of rotational angle. RESULTS: Here, we present an analysis of the relationship between rotational angles and lipid exposure and a support-vector-machine method, called TMexpo, for predicting both structural features from sequences. First, we observed from the development set of 89 protein chains that the lipid exposure, i.e., the relative accessible surface area (rASA) of residues in the lipid environment, generated from high-resolution protein structures could infer the rotational angles with a mean absolute angular error (MAAE) of 46.32˚. More importantly, the predicted rASA from TMexpo achieved an MAAE of 51.05˚, which is better than 71.47˚ obtained by the best of the compared hydrophobicity scales. Lastly, TMexpo outperformed the compared methods in rASA prediction on the independent test set of 21 protein chains and achieved an overall Matthew's correlation coefficient, accuracy, sensitivity, specificity, and precision of 0.51, 75.26%, 81.30%, 69.15%, and 72.73%, respectively. TMexpo is publicly available at http://bio-cluster.iis.sinica.edu.tw/TMexpo. CONCLUSIONS: TMexpo can better predict rASA and rotational angles than the compared methods. When rotational angles can be accurately predicted, free modeling of transmembrane protein structures in turn may benefit from a reduced complexity in ensembles with a significantly less number of packing arrangements. Furthermore, sequence-based prediction of both rotational angle and lipid exposure can provide essential information when high-resolution structures are unavailable and contribute to experimental design to elucidate transmembrane protein functions.

MOTIVATION: Helix-helix interactions play a critical role in the structure assembly, stability and function of membrane proteins. On the molecular level, the interactions are mediated by one or more residue contacts. Although previous studies focused on helix-packing patterns and sequence motifs, few of them developed methods specifically for contact prediction. RESULTS: We present a new hierarchical framework for contact prediction, with an application in membrane proteins. The hierarchical scheme consists of two levels: in the first level, contact residues are predicted from the sequence and their pairing relationships are further predicted in the second level. Statistical analyses on contact propensities are combined with other sequence and structural information for training the support vector machine classifiers. Evaluated on 52 protein chains using leave-one-out cross validation (LOOCV) and an independent test set of 14 protein chains, the two-level approach consistently improves the conventional direct approach in prediction accuracy, with 80% reduction of input for prediction. Furthermore, the predicted contacts are then used to infer interactions between pairs of helices. When at least three predicted contacts are required for an inferred interaction, the accuracy, sensitivity and specificity are 56%, 40% and 89%, respectively. Our results demonstrate that a hierarchical framework can be applied to eliminate false positives (FP) while reducing computational complexity in predicting contacts. Together with the estimated contact propensities, this method can be used to gain insights into helix-packing in membrane proteins.

BACKGROUND: Protein subcellular localization is crucial for genome annotation, protein function prediction, and drug discovery. Determination of subcellular localization using experimental approaches is time-consuming; thus, computational approaches become highly desirable. Extensive studies of localization prediction have led to the development of several methods including composition-based and homology-based methods. However, their performance might be significantly degraded if homologous sequences are not detected. Moreover, methods that integrate various features could suffer from the problem of low coverage in high-throughput proteomic analyses due to the lack of information to characterize unknown proteins. RESULTS: We propose a hybrid prediction method for Gram-negative bacteria that combines a one-versus-one support vector machines (SVM) model and a structural homology approach. The SVM model comprises a number of binary classifiers, in which biological features derived from Gram-negative bacteria translocation pathways are incorporated. In the structural homology approach, we employ secondary structure alignment for structural similarity comparison and assign the known localization of the top-ranked protein as the predicted localization of a query protein. The hybrid method achieves overall accuracy of 93.7% and 93.2% using ten-fold cross-validation on the benchmark data sets. In the assessment of the evaluation data sets, our method also attains accurate prediction accuracy of 84.0%, especially when testing on sequences with a low level of homology to the training data. A three-way data split procedure is also incorporated to prevent overestimation of the predictive performance. In addition, we show that the prediction accuracy should be approximately 85% for non-redundant data sets of sequence identity less than 30%. CONCLUSION: Our results demonstrate that biological features derived from Gram-negative bacteria translocation pathways yield a significant improvement. The biological features are interpretable and can be applied in advanced analyses and experimental designs. Moreover, the overall accuracy of combining the structural homology approach is further improved, which suggests that structural conservation could be a useful indicator for inferring localization in addition to sequence homology. The proposed method can be used in large-scale analyses of proteomes.