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, 【要旨】

Online bipartite matching has attracted much attention due to its importance in various applications such as advertising, ride-sharing, and crowdsourcing. In most online matching problems, the rewards and node arrival probabilities are given in advance and are not controllable. However, many real-world matching services require them to be controllable and the decision-maker faces a non-trivial problem of optimizing them. In this study, we formulate a new optimization problem, Online Matching with Controllable Rewards and Arrival probabilities (OM-CRA), to simultaneously determine not only the matching strategy but also the rewards and arrival probabilities. Even though our problem is more complex than the existing ones, we propose a fast 1/2-approximation algorithm for OM-CRA. The proposed approach transforms OM-CRA to a saddle-point problem by approximating the objective function, and then solves it by the Primal-Dual Hybrid Gradient (PDHG) method with acceleration through the use of the problem structure. In simulations on real data from crowdsourcing and ride-sharing platforms, we show that the proposed algorithm can find solutions with high total rewards in practical times.

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.

The recent enhancement of taxi dispatch services with information technology has enabled data-driven pricing and dispatch. However, existing studies failed to address differences in individual priorities as regards money savings and time savings, leading to non-optimal taxi pricing and dispatch. In this paper, we formulate a new optimization problem that yields optimized price and time proposals for each requester according to their priorities. To consider the requester’s priorities, we introduce an individual requester’s acceptance probability model for price and required time, which is widely used in transportation economics. The proposals of price and time combinations yielded by our method enhance both the requester’s satisfaction and the service provider’s profit. Since the optimization problem is difficult to solve because its objective values are hard to evaluate and discontinuous, we construct a fast approximation algorithm by utilizing the characteristics of the problem. Simulations using real-world datasets show that the proposed framework increases both the requester’s satisfaction and service provider’s profit.

Tomato susceptibility/resistance to stem canker disease caused by Alternaria alternata f. sp. lycopersici and its pathogenic factor AAL-toxin is determined by the presence of the Asc1 gene. Several cultivars of commercial tomato (Solanum lycopersicum var. lycopersicum, SLL) are reported to have a mutation in Asc1, resulting in their susceptibility to AAL-toxin. We evaluated 119 ancestral tomato accessions including S. pimpinellifolium (SP), S. lycopersicum var. cerasiforme (SLC) and S. lycopersicum var. lycopersicum &ldquo, jitomate criollo&rdquo, (SLJ) for AAL-toxin susceptibility. Three accessions, SP PER018805, SLC PER018894, and SLJ M5-3, were susceptible to AAL-toxin. SLC PER018894 and SLJ M5-3 had a two-nucleotide deletion (nt 854_855del) in Asc1 identical to that found in SLL cv. Aichi-first. Another mutation (nt 931_932insT) that may confer AAL-toxin susceptibility was identified in SP PER018805. In the phylogenetic tree based on the 18 COSII sequences, a clade (S3) is composed of SP, including the AAL-toxin susceptible PER018805, and SLC. AAL-toxin susceptible SLC PER018894 and SLJ M5-3 were in Clade S2 with SLL cultivars. As SLC is thought to be the ancestor of SLL, and SLJ is an intermediate tomato between SLC and SLL, Asc1s with / without the mutation seem to have been inherited throughout the history of tomato domestication and breeding.

Video magnification methods can magnify and reveal subtle changes invisible to the naked eye. However, in such subtle changes, meaningful ones caused by physical and natural phenomena are mixed with non-meaningful ones caused by photographic noise. Therefore, current methods often produce noisy and misleading magnification outputs due to the non-meaningful subtle changes. For detecting only meaningful subtle changes, several methods have been proposed but require human manipulations, additional resources, or input video scene limitations. In this paper, we present a novel method using fractional anisotropy (FA) to detect only meaningful subtle changes without the aforementioned requirements. FA has been used in neuroscience to evaluate anisotropic diffusion of water molecules in the body. On the basis of our observation that temporal distribution of meaningful subtle changes more clearly indicates anisotropic diffusion than that of non-meaningful ones, we used FA to design a fractional anisotropic filter that passes only meaningful subtle changes. Using the filter enables our method to obtain better and more impressive magnification results than those obtained with state-of-the-art methods.

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

G protein-coupled receptors (GPCRs) are a large transmembrane receptor superfamily that is involved in many cellular signaling pathways. In the present study, GPCR-family genes from the toxigenic and necrotrophic plant pathogen Alternaria alternata were cloned and characterized. Three GPCR-encoding genes, AaGPR1, AaGPR2, and AaGPR3 were identified in the draft genomic data of the A. alternata tomato pathotype, which produces the host-specific AAL-toxin. AaGPR1, AaGPR2, and AaGPR3 each encodes a protein containing a seven transmembrane domain that is characteristic of GPCRs. Targeted deletion of AaGPR1, AaGPR2, or AaGPR3 in the A. alternata tomato pathotype was conducted to understand the influence of G-protein signaling mechanisms on developmental processes and virulence of this pathogen. No changes in colony morphology or AAL-toxin production were observed for the deletion strain ΔAaGPR1, 2, and 3, compared with the wild-type strain. However, one deletion strain, ΔAaGPR3, exhibited aberrant conidial morphology including decreased conidial length and beak formation. The ability to induce the formation of necrotic lesions on susceptible leaves also significantly decreased in ΔAaGPR3, indicating a reduction in virulence. These defects are similar to the phenotypes found for the Gα gene (AGA1) mutant of A. alternata. These results indicate that the G-protein signal transduction pathway appears to be involved in conidial development and virulence of A. alternata.

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.

Trichoderma harzianum, a biocontrol agent for various plant pathogens, is known to degrade fungal cell walls; this mycoparasitism is believed to require secretion of cell-wall-degrading enzymes against host pathogens. In this study, we identified a homologue of yeast SNF1 (sucrose nonfermenting 1) encoding protein kinase in T. harzianum (ThSNF1) by draft genome sequencing of strain T36. Targeted gene disruption of ThSNF1 was performed using the PEG method with fusion PCR products. Growth of mutant ΔThSNF1 was markedly less than for the wild-type strain on minimal medium with chitin as a carbon source. The mutant exhibited reduced expression of the genes encoding chitinase and polygalacturonase and markedly reduced spore production. Mycoparasitism against plant pathogens such as Fusarium oxysporum f. sp. cubense (Panama disease) and Fusarium graminearum (Fusarium head blight) was clearly impaired in the mutant. The results suggest that ThSNF1 is critical for asexual development, utilization of certain carbon sources and virulence on fungi, and is therefore important for the biocontrol ability of T. harzianum.

Native Trichoderma spp. were isolated from agricultural fields in several regions of Ecuador. These isolates were characterized via morphological observation as well as molecular phylogenetic analysis based on DNA sequences of the rDNA internal transcribed spacer region, elongation factor-1α gene and RNA polymerase subunit II gene. Fifteen native Trichoderma spp. were identified as T. harzianum, T. asperellum, T. virens and T. reesei. Some of these strains showed strong antagonistic activities against several important pathogens in Ecuador, such as Fusarium oxysporum f. sp. cubense (Panama disease) and Mycosphaerella fijiensis (black Sigatoka) on banana, as well as Moniliophthora roreri (frosty pod rot) and Moniliophthora perniciosa (witches’ broom disease) on cacao. The isolates also showed inhibitory effects on in vitro colony growth tests against Japanese isolates of Fusarium oxysporum f. sp. lycopersici, Alternaria alternata and Rosellinia necatrix. The native Trichoderma strains characterized here are potential biocontrol agents against important pathogens of banana and cacao in Ecuador.

We present a taxonomic study of ‘group Favolus’ and related species in Polyporus. Phylogenetic analyses of nurLSU and ITS regions revealed that the infrageneric ‘group Favolus’ is divided into two main clades. Fungi within the group share laterally stipitate basidiocarps, with non-crustose stipe surfaces, and are distinguishable by the morphology of the pileus surface. One clade is characterized by species with hyaline to brown cutis, composed of hyaline to brown agglutinated generative hyphae. The other clade accommodates species with radially striate pileus, and lacks any distinct cutis of agglutinated hyphae. We propose Neofavolus gen. nov., typified by N. alveolaris, for the former clade, and revise the genus Favolus, typified by F. brasiliensis, for the latter clade. Neofavolus includes N. mikawai and N. cremeoalbidus sp. nov., known only from temperate eastern Asia, in addition to N. alveolaris. Favolus includes members of the Polyporus grammocephalus complex, the P. tenuiculus complex, and P. pseudobetulinus. We reveal that the polypore known as ‘P. grammocephalus’ in Asia includes F. acervatus and F. emerici (= P. grammocephalus), whereas ‘P. tenuiculus’ includes three distinct species; F. brasiliensis from tropical America, and F. spathulatus and F. roseus from tropical Asia. Detailed descriptions and illustrations are provided for the accepted species in Favolus and Neofavolus.

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

The tomato pathotype of Alternaria alternata (A. arborescens) produces the dark brown to black pigment melanin, which accumulates in the cell walls of hyphae and conidia. Melanin has been implicated as a pathogenicity factor in some phytopathogenic fungi. Here, two genes of the tomato pathotype for melanin biosynthesis, ALM1 and BRM2-1, which encode a polyketide synthetase and a 1,3,8-trihydroxynaphthalene (THN) reductase, respectively, have been cloned and disrupted in the pathogen. The gene-disrupted mutants, alm1 and brm2-1, had albino and brown phenotypes, respectively. The wild-type and the mutants caused the same necrotic lesions on the leaves after inoculation with spores. These results suggest that melanin is unlikely to play a direct role in pathogenicity in the tomato pathotype A. alternata. Scanning electron microscopy revealed that the conidia of both mutants have much smoother surfaces in comparison to the wild-type. The conidia of those mutants were more sensitive to UV light than those of the wild-type, demonstrating that melanin confers UV tolerance.

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.

To analyze the genetics of host-specific toxin production and its relation to the specific pathogenicity of a mitosporic fungus Alternaria alternata, we developed a protoplast fusion system. Protoplasts of drug-resistant transformants of the A. alternata tomato pathotype (AAL-toxin producer) and A. alternata strawberry pathotype (AF-toxin producer) were fused by electrofusion. Of five fusion strains examined, two strains were pathogenic on both tomato and strawberry host plants, whereas the rest of the fusion strains were pathogenic only on tomato. Pulsed-field gel electrophoresis analysis demonstrated that the hybrid strains pathogenic on both tomato and strawberry carry 1.0- and 1.05-Mb conditionally dispensable (CD) chromosomes derived, respectively, from the parental strains of the tomato and strawberry pathotypes. On the other hand, the fusion strains appeared to maintain only a single homologous chromosome derived from one of the parental strain in the case of essential chromosomes (A chromosomes). The results suggest that fusion strains between two different pathotypes of A. alternata might be haploid resulting from the deletion of extra sets of essential chromosomes in the fused nuclei, whereas the CD chromosomes derived from each parental strain could be maintained stably in a new genetic background with an expanded range of pathogenicity.

Fungi produce a diverse array of toxins that contribute both positively and negatively to agriculture. We describe phytotoxins which have defined roles in plant disease, as well as mycotoxins which generally have no direct role in disease but have significant impacts on animals that feed on infected host plants. We have included examples of host-specific phytotoxins which act upon a very narrow range of susceptible host genotypes, and non-specific phytotoxins which can affect a wide range of plants. We also describe fungal secondary metabolites that underpin certain mutualistic symbioses. Toxins are described based on their core biosynthesis, and include agriculturally important examples of non-ribosomally synthesised peptides, polyketide-based peptides, proteinaceous phytotoxins, sesquiterpenoid-containing compounds and miscellaneaous toxins of herbivores. The role of each toxin in the plant–fungus interaction, as well as the biochemistry and molecular basis of toxin biosynthesis, will be described.

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.