Abstract Connectivity is an important parameter to measure fault-tolerance of networks. As a generalization, structure connectivity and substructure connectivity of networks were proposed. For connected graphs $G$ and $H$, the $H$-structure connectivity $\kappa (G; H)$ (resp. $H$-substructure connectivity $\kappa ^{s}(G; H)$) of $G$ is the minimum cardinality of a set of subgraphs $\mathcal{F}$ of $G$ that each is isomorphic to $H$ (resp. a connected subgraph of $H$) such that $G-\mathcal{F}$ is disconnected or the singleton. $n$-dimensional folded cross cube, $FCQ_{n}$, is a network obtained by adding edges to $n$-dimensional cross cubes. In this paper, we study star, path, and cycle structure connectivity and substructure connectivity of $FCQ_{n}$, where $n\geq 8$. For star ($K_{1,m}$) structure, we get that $\kappa (FCQ_{n}; K_{1, m})=\kappa ^{s}(FCQ_{n}; K_{1, m})=\lceil \frac{n + 1}{2} \rceil $ for $2 \leq m \leq \frac{n}{2}$. For path ($P_{k}$) structure, we show that for $3\leq k\leq n+1$, if $k$ is odd, then $\kappa (FCQ_{n}; P_{k})=\kappa ^{s}(FCQ_{n}; P_{k})=\lceil \frac{2(n + 1)}{k+1}\rceil $; if $k$ is even, then $\kappa (FCQ_{n}; P_{k})=\kappa ^{s}(FCQ_{n}; P_{k})=\lceil \frac{2(n + 1)} {k}\rceil $. For cycle ($C_{k}$) structure, we prove that $\kappa ^(FCQ_{n}; C_{k})=\kappa ^{s}(FCQ_{n}; P_{k})$. Further, we calculate $\kappa ^(FCQ_{n}; C_{2k-1})=\lceil \frac{n+1}{k-1} \rceil $ for $4 \leq k \leq n+2$ and $C_{2k}$-structure connectivity of $FCQ_{n}$ is $\lfloor \frac{n+1}{k} \rfloor +1$ for $6 \leq k\leq n + 1$ and even $k$.

The notion of forcing number for a perfect matching or innate degree of freedom for a Kekulé structure was introduced by Randić and Klein in 1980s, which plays an important role in the resonance theory in organic chemistry. Over the past four decades, some theoretical chemists and mathematicians have been attracted to investigate the effects in some chemical graphs and the graph-theoretical problems in general graphs. Recently some derived concepts and related problems have also been raised successively, such as anti-forcing number of a perfect matching, global forcing number, complete forcing number, etc. This survey will present recent progress on the minimum and maximum (anti-) forcing numbers, (anti-) forcing spectra and (anti-) forcing polynomials of perfect matchings of graphs, and global forcing and complete forcing numbers with their relations, as well as some open problems and conjectures.

Abstract For connected graphs $G$ and $H$, the $H$-structure connectivity $\kappa (G; H)$ (resp. $H$-substructure connectivity $\kappa ^{s}(G; H)$) of $G$ is the minimum cardinality of a set of subgraphs $\mathcal{F}$ of $G$ such that each is isomorphic to $H$ (resp. to a connected subgraph of $H$) so that $G-\mathcal{F}$ is disconnected or singleton. In this paper, we consider $P_t$-structure connectivity and $P_t$-substructure connectivity of augmented $k$-ary $n$-cubes $AQ_{n,k}$ for $n\geq 2$, $k\geq 3$ and $1\leq t\leq 4n-2$. We obtain that $\kappa (AQ_{n,k}; P_t)=\kappa ^s(AQ_{n,k}; P_t)=\frac{4n-2}{t}+1$ for $t\mid 4n-2$, $t\nmid 2n-1$, $t>6$, $n\geq 3$ and $k\geq 4$; $\kappa (AQ_{n,k}; P_t)=\kappa ^s(AQ_{n,k}; P_t)=\lceil \frac{4n-2}{t}\rceil $, in other cases.

Lactic acid bacteria consortia are commonly present in food, and some of these bacteria possess probiotic properties. However, discovery and experimental validation of probiotics require extensive time and effort. Therefore, it is of great interest to develop effective screening methods for identifying probiotics. Advances in sequencing technology have generated massive genomic data, enabling us to create a machine learning-based platform for such purpose in this work. This study first selected a comprehensive probiotics genome dataset from the probiotic database (PROBIO) and literature surveys. Then, k-mer (from 2 to 8) compositional analysis was performed, revealing diverse oligonucleotide composition in strain genomes and apparently more probiotic (P-) features in probiotic genomes than non-probiotic genomes. To reduce noise and improve computational efficiency, 87 376 k-mers were refined by an incremental feature selection (IFS) method, and the model achieved the maximum accuracy level at 184 core features, with a high prediction accuracy (97.77%) and area under the curve (98.00%). Functional genomic analysis using annotations from gene ontology (GO), Kyoto Encyclopedia of Genes and Genomes (KEGG) and Rapid Annotation using Subsystem Technology (RAST) databases, as well as analysis of genes associated with host gastrointestinal survival/settlement, carbohydrate utilization, drug resistance and virulence factors, revealed that the distribution of P-features was biased toward genes/pathways related to probiotic function. Our results suggest that the role of probiotics is not determined by a single gene, but by a combination of k-mer genomic components, providing new insights into the identification and underlying mechanisms of probiotics. This work created a novel and free online bioinformatic tool, iProbiotics, which would facilitate rapid screening for probiotics.

BACKGROUND: Microbial communities in the human body, also known as human microbiota, impact human health, such as colorectal cancer (CRC). However, the different roles that microbial communities play in healthy and disease hosts remain largely unknown. The microbial communities are typically recorded through the taxa counts of operational taxonomic units (OTUs). The sparsity and high correlations among OTUs pose major challenges for understanding the microbiota-disease relation. Furthermore, the taxa data are structured in the sense that OTUs are related evolutionarily by a hierarchical structure. RESULTS: In this study, we borrow the idea of super-variant from statistical genetics, and propose a new concept called super-taxon to exploit hierarchical structure of taxa for microbiome studies, which is essentially a combination of taxonomic units. Specifically, we model a genus which consists of a set of OTUs at low hierarchy and is designed to reflect both marginal and joint effects of OTUs associated with the risk of CRC to address these issues. We first demonstrate the power of super-taxon in detecting highly correlated OTUs. Then, we identify CRC-associated OTUs in two publicly available datasets via a discovery-validation procedure. Specifically, four species of two genera are found to be associated with CRC: Parvimonas micra, Parvimonas sp., Peptostreptococcus stomatis, and Peptostreptococcus anaerobius. More importantly, for the first time, we report the joint effect of Parvimonas micra and Parvimonas sp. (p = 0.0084) as well as that of Peptostrepto-coccus stomatis and Peptostreptococcus anaerobius (p = 8.21e-06) on CRC. The proposed approach provides a novel and useful tool for identifying disease-related microbes by taking the hierarchical structure of taxa into account and further sheds new lights on their potential joint effects as a community in disease development. CONCLUSIONS: Our work shows that proposed approaches are effective to study the microbiota-disease relation taking into account for the sparsity, hierarchical and correlated structure among microbes.

Abstract As a generalization of vertex connectivity, for connected graphs $G$ and $T$, the $T$-structure connectivity $\kappa (G; T)$ (resp. $T$-substructure connectivity $\kappa ^{s}(G; T)$) of $G$ is the minimum cardinality of a set of subgraphs $F$ of $G$ that each is isomorphic to $T$ (resp. to a connected subgraph of $T$) so that $G-F$ is disconnected. For $n$-dimensional hypercube $Q_{n}$, Lin et al. showed $\kappa (Q_{n};K_{1,1})=\kappa ^{s}(Q_{n};K_{1,1})=n-1$ and $\kappa (Q_{n};K_{1,r})=\kappa ^{s}(Q_{n};K_{1,r})=\lceil \frac{n}{2}\rceil $ for $2\leq r\leq 3$ and $n\geq 3$ (Lin, C.-K., Zhang, L.-L., Fan, J.-X. and Wang, D.-J. (2016) Structure connectivity and substructure connectivity of hypercubes. Theor. Comput. Sci., 634, 97–107). Sabir et al. obtained that $\kappa (Q_{n};K_{1,4})=\kappa ^{s}(Q_{n};K_{1,4})= \lceil \frac{n}{2}\rceil $ for $n\geq 6$ and for $n$-dimensional folded hypercube $FQ_{n}$, $\kappa (FQ_{n};K_{1,1})=\kappa ^{s}(FQ_{n};K_{1,1})=n$, $\kappa (FQ_{n};K_{1,r})=\kappa ^{s}(FQ_{n};K_{1,r})= \lceil \frac{n+1}{2}\rceil $ with $2\leq r\leq 3$ and $n\geq 7$ (Sabir, E. and Meng, J.(2018) Structure fault tolerance of hypercubes and folded hypercubes. Theor. Comput. Sci., 711, 44–55). They proposed an open problem of determining $K_{1,r}$-structure connectivity of $Q_n$ and $FQ_n$ for general $r$. In this paper, we obtain that for each integer $r\geq 2$, $\kappa (Q_{n};K_{1,r})$ $=\kappa ^{s}(Q_{n};K_{1,r})$ $=\lceil \frac{n}{2}\rceil $ and $\kappa (FQ_{n};K_{1,r})=\kappa ^{s}(FQ_{n};K_{1,r})= \lceil \frac{n+1}{2}\rceil $ for all integers $n$ larger than $r$ in quare scale. For $4\leq r\leq 6$, we separately confirm the above result holds for $Q_n$ in the remaining cases.

MOTIVATION: High-throughput screening (HTS) is a vital automation technology in biomedical research in both industry and academia. The well-known Z-factor has been widely used as a gatekeeper to assure assay quality in an HTS study. However, many researchers and users may not have realized that Z-factor has major issues. RESULTS: In this article, the following four major issues are explored and demonstrated so that researchers may use the Z-factor appropriately. First, the Z-factor violates the Pythagorean theorem of statistics. Second, there is no adjustment of sampling error in the application of the Z-factor for quality control (QC) in HTS studies. Third, the expectation of the sample-based Z-factor does not exist. Fourth, the thresholds in the Z-factor-based criterion lack a theoretical basis. Here, an approach to avoid these issues was proposed and new QC criteria under homoscedasticity were constructed so that researchers can choose a statistically grounded criterion for QC in the HTS studies. We implemented this approach in an R package and demonstrated its utility in multiple CRISPR/CAS9 or siRNA HTS studies. AVAILABILITY AND IMPLEMENTATION: The R package qcSSMDhomo is freely available from GitHub: https://github.com/Karena6688/qcSSMDhomo. The file qcSSMDhomo_1.0.0.tar.gz (for Windows) containing qcSSMDhomo is also available at Bioinformatics online. qcSSMDhomo is distributed under the GNU General Public License. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Integration of multiple genetic sources for copy number variation detection (CNV) is a powerful approach to improve the identification of variants associated with complex traits. Although it has been shown that the widely used change point based methods can increase statistical power to identify variants, it remains challenging to effectively detect CNVs with weak signals due to the noisy nature of genotyping intensity data. We previously developed modSaRa, a normal mean-based model on a screening and ranking algorithm for copy number variation identification which presented desirable sensitivity with high computational efficiency. To boost statistical power for the identification of variants, here we present a novel improvement that integrates the relative allelic intensity with external information from empirical statistics with modeling, which we called modSaRa2. RESULTS: Simulation studies illustrated that modSaRa2 markedly improved both sensitivity and specificity over existing methods for analyzing array-based data. The improvement in weak CNV signal detection is the most substantial, while it also simultaneously improves stability when CNV size varies. The application of the new method to a whole genome melanoma dataset identified novel candidate melanoma risk associated deletions on chromosome bands 1p22.2 and duplications on 6p22, 6q25 and 19p13 regions, which may facilitate the understanding of the possible roles of germline copy number variants in the etiology of melanoma. AVAILABILITY AND IMPLEMENTATION: http://c2s2.yale.edu/software/modSaRa2 or https://github.com/FeifeiXiaoUSC/modSaRa2. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

SUMMARY: Chromosomal copy number variation (CNV) refers to a polymorphism that a DNA segment presents deletion or duplication in the population. The computational algorithms developed to identify this type of variation are usually of high computational complexity. Here we present a user-friendly R package, modSaRa, designed to perform copy number variants identification. The package is developed based on a change-point based method with optimal computational complexity and desirable accuracy. The current version of modSaRa package is a comprehensive tool with integration of preprocessing steps and main CNV calling steps. AVAILABILITY AND IMPLEMENTATION: modSaRa is an R package written in R, C ++ and Rcpp and is now freely available for download at http://c2s2.yale.edu/software/modSaRa . CONTACT: [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Copy number variation (CNV) is a type of structural variation, usually defined as genomic segments that are 1 kb or larger, which present variable copy numbers when compared with a reference genome. The screening and ranking algorithm (SaRa) was recently proposed as an efficient approach for multiple change-points detection, which can be applied to CNV detection. However, some practical issues arise from application of SaRa to single nucleotide polymorphism data. RESULTS: In this study, we propose a modified SaRa on CNV detection to address these issues. First, we use the quantile normalization on the original intensities to guarantee that the normal mean model-based SaRa is a robust method. Second, a novel normal mixture model coupled with a modified Bayesian information criterion is proposed for candidate change-point selection and further clustering the potential CNV segments to copy number states. Simulations revealed that the modified SaRa became a robust method for identifying change-points and achieved better performance than the circular binary segmentation (CBS) method. By applying the modified SaRa to real data from the HapMap project, we illustrated its performance on detecting CNV segments. In conclusion, our modified SaRa method improves SaRa theoretically and numerically, for identifying CNVs with high-throughput genotyping data. AVAILABILITY AND IMPLEMENTATION: The modSaRa package is implemented in R program and freely available at http://c2s2.yale.edu/software/modSaRa. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: High-dimensional data are frequently generated in genome-wide association studies (GWAS) and other studies. It is important to identify features such as single nucleotide polymorphisms (SNPs) in GWAS that are associated with a disease. Random forests represent a very useful approach for this purpose, using a variable importance score. This importance score has several shortcomings. We propose an alternative importance measure to overcome those shortcomings. RESULTS: We characterized the effect of multiple SNPs under various models using our proposed importance measure in random forests, which uses maximal conditional chi-square (MCC) as a measure of association between a SNP and the trait conditional on other SNPs. Based on this importance measure, we employed a permutation test to estimate empirical P-values of SNPs. Our method was compared to a univariate test and the permutation test using the Gini and permutation importance. In simulation, the proposed method performed consistently superior to the other methods in identifying of risk SNPs. In a GWAS of age-related macular degeneration, the proposed method confirmed two significant SNPs (at the genome-wide adjusted level of 0.05). Further analysis showed that these two SNPs conformed with a heterogeneity model. Compared with the existing importance measures, the MCC importance measure is more sensitive to complex effects of risk SNPs by utilizing conditional information on different SNPs. The permutation test with the MCC importance measure provides an efficient way to identify candidate SNPs in GWAS and facilitates the understanding of the etiology between genetic variants and complex diseases. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Existing tree and forest methods are powerful bioinformatics tools to explore high dimensional data including high throughput genomic data. However, they cannot deal with the data generated by recent genotyping platforms for single nucleotide polymorphisms due to the massive size of the data and its excessive memory demand. RESULTS: Using the recursive partitioning technique, we developed a new software package, Willows, to maximize the utility of the computer memory and make it feasible to analyze massive genotype data. This package includes three tree-based methods -- classification tree, random forest, and deterministic forest, and can efficiently handle the massive amount of SNP data. In addition, this package can easily set different options (e.g., algorithms and specifications) and predict the class of test samples. CONCLUSION: We developed Willows in a user friendly interface with the goal of maximizing the use of memory, which is critical for analysis of genomic data. The Willows package is well documented and publicly available at (http://c2s2.yale.edu/software/Willows).

A fullerene graph F is a 3-connected plane cubic graph with exactly 12 pentagons and the remaining faces as hexagons. Let M be a perfect matching of F. A cycle C of F is M-alternating if the edges of C appear alternately in and off M. A set $\mathcal{H}$ of disjoint hexagons of F is called a resonant pattern (or sextet pattern) if F has a perfect matching M such that all hexagons in $\mathcal{H}$ are M-alternating. A fullerene graph F is k-resonant if any i ($0\leq i \leq k$) disjoint hexagons of F form a resonant pattern. In this paper, we prove that every hexagon of a fullerene graph is resonant and all leapfrog fullerene graphs are 2-resonant. Further, we show that a 3-resonant fullerene graph has at most 60 vertices and we construct all nine 3-resonant fullerene graphs, which are also k-resonant for every integer $k>3$. Finally, sextet polynomials of the 3-resonant fullerene graphs are computed.

SUMMARY: Existing linkage-analysis methods address binary or quantitative traits. However, many complex diseases and human conditions, particularly behavioral disorders, are rated on ordinal scales. Herein, we introduce, LOT, a tool that performs linkage analysis of ordinal traits for pedigree data. It implements a latent-variable proportional-odds logistic model that relates inheritance patterns to the distribution of the ordinal trait. The likelihood-ratio test is used for testing evidence of linkage. AVAILABILITY: The LOT program is available for download at http://c2s2.yale.edu/software/LOT/

Applying the recently obtained distributive lattice structure on the set of 1-factors, we show that the resonance graphs of any benzenoid systems G, as well as of general plane (weakly) elementary bipartite graphs, are median graphs and thus extend greatly Klavžar et al.'s result. The n-dimensional vectors of nonnegative integers as a labelling for the 1-factors of G with n inner faces are described. The labelling preserves the partial ordering of the above-mentioned lattice and can be transformed into a binary coding for the 1-factors. A simple criterion for such a labelling being binary is given. In particular, Klavžar et al.'s algorithm is modified to generate this binary coding for the 1-factors of a cata-condensed benzenoid system.

An edge-cut S of a connected graph G is called a restricted edge-cut if G-S contains no isolated vertices. The minimum cardinality of all restricted edge-cuts is called the restricted edge-connectivity lambda(G) of G. A graph G is said to be lambda'-optimal if lambda'(G) = xi(G), where (G) is the minimum edge-degree of G. A graph is said to be super-lambda' if every minimum restricted edge-cut isolates an edge. In this paper, first, we improve and generalize the sufficient conditions for lambda'-optimality in arbitrary graphs, bipartite graphs, and graphs with diameter 2, which were given by Hellwig and Volkmann, and show using examples that our results are best possible. Second, we provide a simple proof with less restrictive conditions than in Hellwig and Volkmann's theorem that gives sufficient conditions for lambda'-optimality in bipartite graphs. We conclude by presenting sufficient conditions for arbitrary, bipartite, and triangle-free graphs, and for graphs with diameter 2, to be super-lambda' respectively, and demonstrate that these conditions are best possible. (c) 2007 Wiley Periodicals, Inc.

The rapid advances in high-throughput biotechnologies such as DNA microarrays and mass spectrometry have generated vast amounts of data ranging from gene expression to proteomics data. The large size and complexity involved in analyzing such data demand a significant amount of computing power. High-performance computation (HPC) is an attractive and increasingly affordable approach to help meet this challenge. There is a spectrum of techniques that can be used to achieve computational speedup with varying degrees of impact in terms of how drastic a change is required to allow the software to run on an HPC platform. This paper describes a high- productivity/low-maintenance (HP/LM) approach to HPC that is based on establishing a collaborative relationship between the bioinformaticist and HPC expert that respects the former's codes and minimizes the latter's efforts. The goal of this approach is to make it easy for bioinformatics researchers to continue to make iterative refinements to their programs, while still being able to take advantage of HPC. The paper describes our experience applying these HP/LM techniques in four bioinformatics case studies: (1) genome-wide sequence comparison using Blast, (2) identification of biomarkers based on statistical analysis of large mass spectrometry data sets, (3) complex genetic analysis involving ordinal phenotypes, (4) large-scale assessment of the effect of possible errors in analyzing microarray data. The case studies illustrate how the HP/LM approach can be applied to a range of representative bioinformatics applications and how the approach can lead to significant speedup of computationally intensive bioinformatics applications, while making only modest modifications to the programs themselves.

MOTIVATION: Due to the existence of the loss of synchrony in cell-cycle data sets, standard clustering methods (e.g. k-means), which group open reading frames (ORFs) based on similar expression levels, are deficient unless the temporal pattern of the expression levels of the ORFs is taken into account. METHODS: We propose to improve the performance of the k-means method by assigning a decreasing weight on its variable level and evaluating the 'weighted k-means' on a yeast cell-cycle data set. Protein complexes from a public website are used as biological benchmarks. To compare the k-means clusters with the structures of the protein complexes, we measure the agreement between these two ways of clustering via the adjusted Rand index. RESULTS: Our results show the time-decreasing weight function--exp[-(1/2)(t(2)/C(2))]--which we assign to the variable level of k-means, generally increases the agreement between protein complexes and k-means clusters when C is near the length of two cell cycles.