Summary: Exhaustive detection of multi-loci markers from genome-wide association study datasets is a computationally challenging problem. This paper presents a massively parallel algorithm for finding all significant combinations of alleles and introduces a software tool termed MP-LAMP that can be easily deployed in a cloud platform, such as Amazon Web Service, as well as in an in-house computer cluster. Multi-loci marker detection is an unbalanced tree search problem that cannot be parallelized by simple tree-splitting using generic parallel programming frameworks, such as Map-Reduce. We employ work stealing and periodic reduce-broadcast to decrease the running time almost linearly to the number of cores. Availability and implementation: MP-LAMP is available at https://github.com/tsudalab/mp-lamp. Supplementary information: Supplementary data are available at Bioinformatics online.

One of the major issues in genome-wide association studies is to solve the missing heritability problem. While considering epistatic interactions among multiple SNPs may contribute to solving this problem, existing software cannot detect statistically significant high-order interactions. We propose software named LAMPLINK, which employs a cutting-edge method to enumerate statistically significant SNP combinations from genome-wide case-control data. LAMPLINK is implemented as a set of additional functions to PLINK, and hence existing procedures with PLINK can be applicable. Applied to the 1000 Genomes Project data, LAMPLINK detected a combination of five SNPs that are statistically significantly accumulated in the Japanese population. AVAILABILITY AND IMPLEMENTATION: LAMPLINK is available at http://a-terada.github.io/lamplink/ CONTACT: [email protected] or [email protected] information: Supplementary data are available at Bioinformatics online.

Three or more motifs often work together, and the effects are essential in cellular machinery. However, the scanning of the associations of motifs is limited to single motifs or pairs, as the result of scanning for combinations of three or more motifs often includes no significant results. Even if we find a combination with a very small raw P-value in the scan, the combination is not significant because the adjusted P-value by a multiple testing correction, such as the Bonferroni correction, is larger than the given significance level. While it is known that the Bonferroni correction is a very conservative correction, a few biological experiments have used more sensitive random permutation based multiple testing correction such as Westfall-Young procedure (WY procedure). In this paper, we show that the Bonferroni correction and its modified procedure are too conservative to find statistically significant combinations consisting of three or more motifs, while the WY procedure can detect them. These results suggest that the statistically significant epistatic effects have been overlooked and motivate us to reanalyze the publicly available datasets.

Three or more transcription factors (TFs) often work together, and the combinatorial regulations are essential in cellular machinery. However, it is impossible to discover statistically significant sets of TF binding motifs due to the necessity of the multiple testing procedure. To improve the sensitivity of widely used Bonferroni correction or its modified methods, such as Holm procedure, Westfall-Young permutation procedure (WY-procedure) has often been applied. However, few studies have used WY-procedure for the discoveries of the combinatorial effects of the motifs because of the extremely large computational time. In this paper, we propose an efficient branch-and-bound algorithm to perform WY-procedure to enumerate statistically significant motif combinations. When we use WY-procedure for the combinatorial regulation discovery, finding the minimum P-value from each permuted dataset consumes an enormous amount of time. We show that a combination that has the possibility to achieve the minimum P-value appears with high frequency over the threshold in dataset. This property enables a frequent itemset mining algorithm to efficiently select the candidates to achieve the minimum P-value. Our demonstrations using yeast and human transcriptome datasets show that the proposed algorithm is orders-of-magnitude faster than WY-procedure, and can practically list statistically significant motif combinations even when any combinations are considered.

A gene network is constructed with genes as nodes, and interactions between genes as edges so as to reveal unknown gene functions and relationship. However, nodes and edges of gene networks are usually very numerous. Because of that, it may be difficult to understand relations between genomic functions and gene-gene interactions, if it is visualized by traditional techniques. This paper presents our technique on visualization of gene networks and gene ontology(GO), which summarizes gene functions and attributes. The technique represents the functions defined by GO as colors of nodes, and bundles edges depending on the gene functions to ease visual complication of the network.