Recent epigenetics research has demonstrated that chromatin conformation plays an important role in various aspects of gene regulation. Chromosome Conformation Capture (3C) technology makes it possible to analyze the spatial organization of chromatin in a cell. Several algorithms for three-dimensional reconstruction of chromatin structure from 3C experimental data have been proposed. Compared to other algorithms, ShRec3D, one of the most advanced algorithms, can reconstruct a chromatin model in the shortest time for high-resolution whole-genome experimental data. However, ShRec3D employs a graph shortest path algorithm, which introduces errors in the resulting model. We propose an improved algorithm that optimizes shortest path distances using a genetic algorithm approach. The proposed algorithm and ShRec3D were compared using in silico 3C experimental data. Compared to ShRec3D, the proposed algorithm demonstrated significant improvement relative to the similarity between the algorithm's output and the original model with a reasonable increase to calculation time.

BACKGROUND: Comprehensively understanding the dynamics of biological systems is among the biggest current challenges in biology and medicine. To acquire this understanding, researchers have measured the time-series expression profiles of cell lines of various organisms. Biological technologies have also drastically improved, providing a huge amount of information with support from bioinformatics and systems biology. However, the transitions between the activation and inactivation of gene regulations, at the temporal resolution of single time points, are difficult to extract from time-course gene expression profiles. RESULTS: Our proposed method reports the activation period of each gene regulation from gene expression profiles and a gene regulatory network. The correctness and effectiveness of the method were validated by analyzing the diauxic shift from glucose to lactose in Escherichia coli. The method completely detected the three periods of the shift; 1) consumption of glucose as nutrient source, 2) the period of seeking another nutrient source and 3) consumption of lactose as nutrient source. We then applied the method to mouse adipocyte differentiation data. Cell differentiation into adipocytes is known to involve two waves of the gene regulation cascade, and sub-waves are predicted. From the gene expression profiles of the cell differentiation process from ES to adipose cells (62 time points), our method acquired four periods; three periods covering the two known waves of the cascade, and a final period of gene regulations when the differentiation to adipocytes was completed. CONCLUSIONS: Our proposed method identifies the transitions of gene regulations from time-series gene expression profiles. Dynamic analyses are essential for deep understanding of biological systems and for identifying the causes of the onset of diseases such as diabetes and osteoporosis. The proposed method can greatly contribute to the progress of biology and medicine.

Gene expression profiling has been increasingly used in clinical practice. Integration of expression data across multiple experiments provides better insight into the heterogeneity of the biology being examined. A problem of the data integration, an experimental batch from platform or laboratory sources, remains a barrier to systematically analyzing data across different datasets. Several methods (such as, ComBat) have been proposed to remove batch effects. However, these methods often make assumptions about ideal distribution of the underlying data. Difficulties might be expected when comparing datasets that have fundamentally different (dataset-dependent) distributions. For example, clinical datasets are often collected from patient samples with various disease stages or conditions. Therefore, we have compared several mathematical transformations across many datasets, including the nonparametric Z scaling transformation method (NPZ) we have proposed for clinical use. We selected 2,813 patients with available information on estrogen receptor (ER) status or human epidermal growth factor receptor 2 (HER2) status from 24 Affymetrix HG-U133 (GPL96) or Affymetrix HG-U133 plus 2.0 (GPL570) datasets in the Gene Expression Omnibus database. The microarray expression data were processed with one of the four following methods: Raw (background correction and log transformation only), Microarray Suite 5.0 (MAS5), frozen robust multiarray analysis (fRMA), and radius minimax (RMX). The normalized data were sequentially transformed by using one of the following five methods: untransformed (without transformation), single-array-based transformations (RANK, Z, NPZ, or YuGene). Finally, we compared the ER and HER2 statuses assessed by immunohistochemical (IHC) staining with mRNA expression. We found that single-array-based transformation in addition to normalization improved the concordance rates of the IHC staining. We demonstrated the influence of transformation by using breast cancer samples and showed that adding single-array-based transformations to microarray expression data resulted in stronger correlations with IHC staining.

MOTIVATION: Clustering of protein sequences is widely used for the functional characterization of proteins. However, it is still not easy to cluster distantly-related proteins, which have only regional similarity among their sequences. It is therefore necessary to develop an algorithm for clustering such distantly-related proteins. RESULTS: We have developed a time and space efficient clustering algorithm. It uses a graph representation where its vertices and edges denote proteins and their sequence similarities above a certain cutoff score, respectively. It repeatedly partitions the graph by removing edges that have small weights, which correspond to low sequence similarities. To find the appropriate partitions, we introduce a score combining the normalized cut and a locally minimal cut capacities. Our method is applied to the entire 40,703 human proteins in SWISS-PROT and TrEMBL. The resulting clusters shows a 76% recall (20,529 proteins) of the 26,917 classified by InterPro. It also finds relationships not found by other clustering methods. AVAILABILITY: The complete result of our algorithm for all the human proteins in SWISS-PROT and TrEMBL, and other supplementary information are available at http://motif.ics.es.osaka-u.ac.jp/Ncut-KL/

This paper presents a clustering method for the comparative analysis of genomes and metabolic pathways. Our method consists of several steps: (1) extract linear sequences of metabolic reactions (non-branching pathways) from a network of metabolic pathways, (2) perform pairwise alignments of every pair of non-branching pathways, and (3) explore a set of genes for each aligned non-branching pathways such that those genes encode enzymes of the pathway and the genes are closely located on a genome (such as operons or gene clusters). To measure the similarity between pathways, we formalized a scoring system by using the functional hierarchy of the EC numbers of enzymes. By applying our method to the metabolic pathways in Escherichia coli, we have obtained several pairs of pathways with similar reactions having enzymes encoded by neighbor genes on the E. coli genome. The resulting pathway pairs were mainly found in metabolisms between similar amino acids (tryptophan and histidine) and between similar sugars (fucose and rhamnose).

We propose a strategy using competitive hybridization for DNA computing. DNA computing is a means of solving intractable computation problems such as NP-complete problems. In our strategy, each spot on a DNA microarray represents the candidate solution. The calculation is executed by competitive hybridization of two groups of fluorescent DNA strands. One group represents a situation in which constraints of the problem are satisfied, and another group represents a situation in which constraints of the problems are not satisfied. After competitive hybridization of two groups, the spot with only the former type of fluorescent DNA strands hold "true" solution. We describe the approach to DNA computing by competitive hybridization through SAT problem. The SAT problem is an NP-complete problem in Boolean logic. We also show that our DNA computing can solve optimization problem through MAX-SAT problem. MAX-SAT problem is one of the derivative problems of SAT and it belongs to MAX-SNP-complete and APX-complete.

A gradual neural network (GNN) approach with the improved gradual expansion scheme is proposed for broadcast scheduling in packet radio (PR) networks. A PR network provides data communications services to geographically distributed nodes through a radio channel. A time division multiple access (TDMA) protocol is adopted for the network. Packets are transmitted in repetition of a TDMA cycle, where the delay time in packet broadcasting should be minimized. The proposed gradual expansion scheme resolves the constraints of the problem using neuron inputs and outputs to reduce the computation time. Besides, an additional slot to a TDMA cycle is considered for slot assignments when a valid solution is not obtained within a current cycle. The performance comparison with a conventional GNN and a greedy algorithm shows the effectiveness of the proposed GNN approach.

This paper presents a neuron filter algorithm to satisfy two constraints of the graph-coloring problem through a separated board-level routing problem (s-BLRP) in an FPGA-based logic emulation system. For a rapid prototyping of large scale digital systems, multiple FPGAs provide an efficient logic emulation system, where signals or nets between design partitions embedded on different FPGAs are connected through crossbars. We propose a new neuron filter algorithm to satisfy the two constraints of the problem simultaneously. The simulation results in randomly generated benchmark site instances show that our neuron filter algorithm with the thinning out application provides the better routing capability with the shorter computation time.

In this paper, we propose an improved genetic algorithm for the traveling salesman problem (TSP) by using the "visiting order restriction theorem". The visiting order restriction theorem gives a necessary condition for the shortest tour of TSP on the Euclidean plane by using the convex hull. The convex hull for a set of points S on a plane is defined as the smallest convex polygon that encloses S. In our method, the initial tours are produced to satisfy the necessary condition of the theorem for the shortest path without increasing the computation time. The simulation results using 10 well-known benchmark problems show that our algorithm can find better tour with shorter time than Pal's algorithm (1993).