Bacteria in the human body, particularly in the large intestine, are known to be associated with various diseases. To identify disease-associated bacteria (markers), a typical method is to statistically compare the relative abundance of bacteria between healthy subjects and diseased patients. However, since bacteria do not necessarily cause diseases in isolation, it is also important to focus on the interactions and relationships among bacteria when examining their association with diseases. In fact, although there are common approaches to represent and analyze bacterial interaction relationships as networks, there are limited methods to find bacteria associated with diseases through network-driven analysis. In this paper, we focus on rewiring of the bacterial network and propose a new method for quantifying the rewiring. We then apply the proposed method to a group of colorectal cancer patients. We show that it can identify and detect bacteria that cannot be detected by conventional methods such as abundance comparison. Furthermore, the proposed method is implemented as a general-purpose tool and made available to the general public.

Abstract A graph $$G = (V,E)$$ G = ( V , E ) is a double-threshold graph if there exist a vertex-weight function $$w :V \rightarrow \mathbb {R}$$ w : V → R and two real numbers $$\mathtt {lb}, \mathtt {ub}\in \mathbb {R}$$ lb , ub ∈ R such that $$uv \in E$$ u v ∈ E if and only if $$\mathtt {lb}\le \mathtt {w}(u) + \mathtt {w}(v) \le \mathtt {ub}$$ lb ≤ w ( u ) + w ( v ) ≤ ub . In the literature, those graphs are studied also as the pairwise compatibility graphs that have stars as their underlying trees. We give a new characterization of double-threshold graphs that relates them to bipartite permutation graphs. Using the new characterization, we present a linear-time algorithm for recognizing double-threshold graphs. Prior to our work, the fastest known algorithm by Xiao and Nagamochi [Algorithmica 2020] ran in $$O(n^{3} m)$$ O ( n 3 m ) time, where n and m are the numbers of vertices and edges, respectively.

We propose a new kind of sliding-block puzzle, called Gourds, where the objective is to rearrange 1×2 pieces on a hexagonal grid board of 2n+1 cells with n pieces, using sliding, turning and pivoting moves. This puzzle has a single empty cell on a board and forms a natural extension of the 15-puzzle to include rotational moves. We analyze the puzzle and completely characterize the cases when the puzzle can always be solved. We also study the complexity of determining whether a given set of colored pieces can be placed on a colored hexagonal grid board with matching colors. We show this problem is NP-complete for arbitrarily many colors, but solvable in randomized polynomial time if the number of colors is a fixed constant.

In the economic activities, the central bank has an important role to cover payments of banks, when they are short of funds to clear their debts. For this purpose, the central bank timely puts funds so that the economic activities go smooth. Since payments in this mechanism are processed sequentially, the total amount of funds put by the central bank critically depends on the order of the payments. Then an interest goes to the amount to prepare if the order of the payments can be controlled by the central bank, or if it is determined under the worst case scenario. This motivates us to introduce a brand-new problem, which we call the settlement fund circulation problem. The problems are formulated as follows: Let G=(V,A) be a directed multigraph with a vertex set V and an arc set A. Each arc a\in A is endowed debt d(a)\ge 0, and the debts are settled sequentially under a sequence \pi of arcs. Each vertex v\in V is put fund in the amount of p_{\pi}(v)\ge 0 under the sequence. The minimum/maximum settlement fund circulation problem (Min-SFC/Max-SFC) in a given graph G with debts d: A\rightarrow \mathbb{R}_{+}\cup \{0\} asks to find a bijection \pi:A\to \{1,2,\dots,|A|\} that minimizes/maximizes the total funds \sum _{v\in V}p_{\pi }(v). In this paper, we show that both Min-SFC and Max-SFC are NP-hard; in particular, Min-SFC is (I) strongly NP-hard even if G is (i) a multigraph with |V|=2 or (ii) a simple graph with treewidth at most two,and is (II) (not necessarily strongly) NP-hard for simple trees of diameter four, while it is solvable in polynomial time for stars. Also, we identify several polynomial time solvable cases for both problems.

When we solve a problem, we firstly have no knowledge and gradually acquire some piece of knowledge by observing new data, and at last arrive at complete knowledge for solving the problem. We have a simple form of specific knowledge in the first stage and a complex form of a general one in the final stage. To simulate this kind of learning mechanism, we must combine several kinds of learning methods in several stages. We proposed a method of not only reconstructing rules and switching reasoning methods in each knowledge representation but also switching rule generation methods in several knowledge representation. We simulated the method by applying to the iris classification problem.

We present several results on de Morgan algebras and Kleene algebras of fuzzy logic. The main results include (1) a necessary and sufficient condition for a de Morgan algebra to be a Kleene algebra, (2) equivalence of some expressions, (3) some properties about de Morgan algebras with sup W/sup +/ and inf W/sup -/, (4) some properties of the de Morgan algebras which satisfy certain special conditions, (5) a method to obtain all fixed points of a de Morgan algebra and (6) extensions of some theorems on complete de Morgan algebras that have fixed points to the general case.