We propose an acceleration method for phenotypic analysis of monozygotic twins based on joint investigation of single-nucleotide polymorphisms (SNPs) and methylated cytosine-phosphate-guanine (mCpG) sites. The phenotypic analysis consists of the following two procedures: (1) identification of mCpG-SNP pairs closely located in base sequences and (2) t-tests on the identified mCpG-SNPs. The proposed method accelerates these procedures with bitwise search and batched computation. The bitwise search exploits the bit-level parallelism of the first procedure by simultaneously processing every 64 bases in sequences of over three billion bases. On the other hand, the batched computation exploits the data-parallelism of the second procedure, where millions of small t-tests must be processed for phenotypic analysis. Experimental results show that the proposed method on a single-core CPU is approximately 3.8 times faster than a previous method. Furthermore, the proposed method achieves a 14.6× speedup on two 10-core CPUs. We therefore believe that the proposed method is useful for accelerating genomewide association analysis, where large-scale data should be investigated in short time.

Abstract This article describes a node capacitated in‐tree packing problem. The input consists of a directed graph, a root node, a node capacity function, and edge consumption functions. The problem is to find the maximum number of rooted in‐trees, such that the total consumption of in‐trees at each node does not exceed the capacity of the node. The problem is one of the network lifetime problems that are among the most important issues in the context of sensor networks. We establish the computational complexity of the problem under various restrictions on consumption functions and graphs. For example, we consider general graphs, acyclic graphs, and complete graphs embedded in the d ‐dimensional space \input amssym ${\Bbb{R}}^d$ having edge consumption functions depending only on distances between end nodes. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012