Search

Collective graphical model (CGM) is a probabilistic model that provides a framework for analyzing aggregated count data. Maximum a posteriori (MAP) inference of unobserved variables under given observations is one of the essential operations in CGM. Because the MAP inference problem is known to be NP-hard in general, the current mainstream approach is to solve an alternative problem obtained by approximating the objective function and applying continuous relaxation. However, this approach has two significant drawbacks. First, the quality of the solution deteriorates when the values in the count data are negligible due to the inaccuracy of Stirling’s approximation. Second, the application of continuous relaxation causes the violation of integrality constraints. This paper proposes novel algorithms for MAP inference in CGMs on path graphs to overcome these problems. Our method is based on the discrete difference of convex algorithm (DCA); DCA is a general framework to minimize the sum of a convex function and a concave function by repeatedly minimizing surrogate functions. Utilizing the particular structure of path graphs, we efficiently solve the surrogate function minimization by minimum convex cost flow algorithms. Furthermore, our approach also leads to a new method of solving another important task; MAP inference of the sample size in CGM on path graphs. Our method is naturally applicable to this task, allowing us to design very efficient algorithms. Experimental results on synthetic and real-world datasets show the effectiveness of the proposed algorithms.

2022, 【要旨】

The research field of stochastic matching has yielded many developments for various applications. In most stochastic matching problems, the probability distributions inherent in the nodes and edges are set a priori, and are not controllable. However, many matching services have options, which we call control variables, that affect the probability distributions and thus what constitutes an optimum matching. Although several methods for optimizing the values of the control variables have been developed, their optimization in consideration of the matching problem is still in its infancy. In this paper, we formulate an optimization problem for determining the values of the control variables so as to maximize the expected value of matching weights. Since this problem involves hard to evaluate objective values and is non-convex, we construct an approximation algorithm via a minimum-cost flow algorithm that can find 3-approximation solutions rapidly. Simulations on real data from a ride-hailing platform and a crowd-sourcing market show that the proposed method can find solutions with high profits of the service provider in practical time.

Collective Flow Diffusion Model (CFDM) is a general framework to find the hidden movements underlying aggregated population data. The key procedure in CFDM analysis is MAP inference of hidden variables. Unfortunately, existing approaches fail to offer exact MAP inferences, only approximate versions, and take a lot of computation time when applied to large scale problems. In this paper, we propose an exact and efficient method for MAP inference in CFDM. Our key idea is formulating the MAP inference problem as a combinatorial optimization problem called Minimum Convex Cost Flow Problem (C-MCFP) with no approximation or continuous relaxation. On the basis of this formulation, we propose an efficient inference method that employs the C-MCFP algorithm as a subroutine. Our experiments on synthetic and real datasets show that the proposed method is effective both in single MAP inference and people flow estimation with EM algorithm.

Alternaria alternata includes seven pathogenic variants, called pathotypes, which produce host-selective toxins (HSTs) as determinant factors for pathogenicity. The gene clusters for HST biosynthesis were identified from six pathotypes (Japanese pear, strawberry, tangerine, apple, tomato and rough lemon) and were found to reside on small chromosomes of

The Southern corn leaf blight (SCLB) epidemic of 1970 devastated fields of T-cytoplasm corn planted in monoculture throughout the eastern United States. The epidemic was driven by race T, a previously unseen race of Cochliobolus heterostrophus. A second fungus, Phyllosticta zeae-maydis, with the same biological specificity, appeared coincidentally. Race T produces T-toxin, while Phyllosticta zeae-maydis produces PM-toxin, both host-selective polyketide toxins necessary for supervirulence. The present abundance of genome sequences offers an opportunity to tackle the evolutionary origins of T- and PM- toxin biosynthetic genes, previously thought unique to these species. Using the C. heterostrophus genes as probes, we identified orthologs in six additional Dothideomycete and three Eurotiomycete species. In stark contrast to the genetically fragmented race T Tox1 locus that encodes these genes, all newly found Tox1-like genes in other species reside at a single collinear locus. This compact arrangement, phylogenetic analyses, comparisons of Tox1 protein tree topology to a species tree, and Tox1 gene characteristics suggest that the locus is ancient and that some species, including C. heterostrophus, gained Tox1 by horizontal gene transfer. C. heterostrophus and Phyllosticta zeae-maydis did not exchange Tox1 DNA at the time of the SCLB epidemic, but how they acquired Tox1 remains uncertain. The presence of additional genes in Tox1-like clusters of other species, although not in C. heterostrophus and Phyllosticta zeae-maydis, suggests that the metabolites produced differ from T- and PM-toxin.

Alternaria alternata tomato pathotypeは，宿主特異的AAL毒素生産によりトマトアルターナリア茎枯病を引き起こす．AAL毒素はマイコトキシン フモニシンの構造類縁体であり，その生物活性も類似する．罹病植物組織内における病原菌の伸長と産生された毒素の確認は，毒素の病理学的重要性とリスクの評価のために重要である．抵抗性植物品種上において，病原菌および毒素は接種部位のみに局在していた．一方，感受性品種上では，毒素の広範な分布と病原菌の伸長が確認された．本研究の結果から，AAL毒素の病理学的重要性が確認されるとともに，罹病トマトにおける毒素による汚染リスクの可能性が示唆された．

The tomato pathotype of Alternaria alternata produces host-specific AAL toxin and causes Alternaria stem canker on tomato. A polyketide synthetase (PKS) gene, ALT1 , which is involved in AAL toxin biosynthesis, resides on a 1.0-Mb conditionally dispensable chromosome (CDC) found only in the pathogenic and AAL toxin-producing strains. Genomic sequences of ALT1 and another PKS gene, both of which reside on the CDC in the tomato pathotype strains, were compared to those of tomato pathotype strains collected worldwide. This revealed that the sequences of both CDC genes were identical among five A. alternata tomato pathotype strains having different geographical origins. On the other hand, the sequences of other genes located on chromosomes other than the CDC are not identical in each strain, indicating that the origin of the CDC might be different from that of other chromosomes in the tomato pathotype. Telomere fingerprinting and restriction fragment length polymorphism analyses of the A. alternata strains also indicated that the CDCs in the tomato pathotype strains were identical, although the genetic backgrounds of the strains differed. A hybrid strain between two different pathotypes was shown to harbor the CDCs derived from both parental strains with an expanded range of pathogenicity, indicating that CDCs can be transmitted from one strain to another and stably maintained in the new genome. We propose a hypothesis whereby the ability to produce AAL toxin and to infect a plant could potentially be distributed among A. alternata strains by horizontal transfer of an entire pathogenicity chromosome. This could provide a possible mechanism by which new pathogens arise in nature.

The tomato pathotype of Alternaria alternata produces a host-specific AAL-toxin and causes Alternaria stem canker on susceptible tomato cultivars. AAL-toxin is a sphinganine-analog mycotoxin which induces apoptotic cell death in tomato cells and mammalian cells by inhibiting ceramide biosynthesis. Insensitivity to the AAL-toxin in resistant tomatoes and other plants is conferred by the Asc1 gene, a homolog of the yeast ceramide synthase gene Lag1 . The ALT7 gene, a putative acyl-CoA-dependent ceramide synthase, was found to be located in the AAL-toxin biosynthetic ( ALT ) gene cluster of the tomato pathotype of A. alternata . ALT7 and Asc1 have the TLC (TRAM/Lag1/ CLN8) domain characteristic of proteins involved in ceramide biosynthesis and are members of the LASS/Lag family. To test the hypothesis that ALT7 and Asc1 , both of which are Lag1 ceramide synthase gene homologs, might share a common biological function as toxin tolerance genes, we have cloned and characterized ALT7. ALT7 -deleted mutants were generated to investigate the effects of the deletion on vegetative growth, sporulation, toxin-sensitivity, toxin-production and pathogenicity. The deletion of ALT7 has no deleterious effect on the toxin-producing pathogen, indicating that the gene does not act as a resistance/self-tolerance factor against the toxin in the toxin biosynthetic gene cluster.

Host-selective toxins (HSTs) produced by fungal plant pathogens are generally low-molecular-weight secondary metabolites with a diverse range of structures that function as effectors controlling pathogenicity or virulence in certain plant–pathogen interactions. There are now seven known diseases caused by Alternaria alternata in which HSTs are responsible for fungal pathogenesis. The pathogens have been defined as pathotypes of A. alternata because of morphological similarity but pathological differences. Chemical structures of HSTs from six pathotypes have been determined. The role of A. alternata HSTs in pathogenesis has been studied extensively, and discovery of the release of HSTs from germinating conidia prior to penetration aids in understanding the early participation of HSTs to induce susceptibility of host cells by suppressing their defence reactions. Many attempts have been made to find the target sites of A. alternata HSTs, and four cellular components, plasma membrane, mitochondrion, chloroplast and a metabolically important enzyme, have been identified as the primary sites of each HST action, leading to elucidation of the molecular mechanisms of HST sensitivity in host plants. Studies of the molecular genetics of HST production have identified supernumerary chromosomes encoding HST gene clusters and have provided new insights into the evolution of A. alternata pathotypes.