作者：
Kimura, KouichiKoike, AsakoHitachi Ltd
Biosyst Res Dept Ctr Technol Innovat Healthcare 1-280 Higashi Koigakubo Kokubunji Tokyo 1858601 Japan Hitachi Ltd
Future Investment Div Chiyoda Ku 1-6-6 Marunouchi Tokyo 1008280 Japan
The Burrows-Wheeler transform (BWT) of short-read data has unexplored potential utilities, such as for efficient and sensitive variation analysis against multiple reference genome sequences, because it does not depend...
详细信息
The Burrows-Wheeler transform (BWT) of short-read data has unexplored potential utilities, such as for efficient and sensitive variation analysis against multiple reference genome sequences, because it does not depend on any particular reference genome sequence, unlike conventional mapping-based methods. However, since the amount of read data is generally much larger than the size of the reference sequence, computation of the BWT of reads is not easy, and this hampers development of potential applications. For the alleviation of this problem, a new method of computing the BWT of reads in parallel is proposed. The BWT, corresponding to a sorted list of suffixes of reads, is constructed incrementally by successively including longer and longer suffixes. The working data is divided into more than 10,000 "blocks" corresponding to sublists of suffixes with the same prefixes. Thousands of groups of blocks can be processed in parallel while making exclusive writes and concurrent reads into a shared memory. Reads and writes are basically sequential, and the read concurrency is limited to two. Thus, a fine-grained parallelism, referred to as prefix parallelism, is expected to work efficiently. The time complexity for processing n reads of length l is O(nl(2)). On actual biological DNA sequence data of about 100 Gbp with a read length of 100 bp (base pairs), a tentative implementation of the proposed method took less than an hour on a single-node computer;i.e., it was about three times faster than one of the fastest programs developed so far.
In this paper, we provide a theoretical foundation for the problem of network localization in which some nodes know their locations and other nodes determine their locations by measuring the distances to their neighbo...
详细信息
In this paper, we provide a theoretical foundation for the problem of network localization in which some nodes know their locations and other nodes determine their locations by measuring the distances to their neighbors. We construct grounded graphs to model network localization and apply graph rigidity theory to test the conditions for unique localizability and to construct uniquely localizable networks. We further study the computational complexity of network localization and investigate a subclass of grounded graphs where localization can be computed efficiently. We conclude with a discussion of localization in sensor networks where the sensors are placed randomly.
We describe TreeDT, a novel association-based gene mapping method. Given a set of disease-associated haplotypes and a set of control haplotypes, TreeDT predicts likely locations of a disease susceptibility gene. TreeD...
详细信息
We describe TreeDT, a novel association-based gene mapping method. Given a set of disease-associated haplotypes and a set of control haplotypes, TreeDT predicts likely locations of a disease susceptibility gene. TreeDT extracts, essentially in the form of haplotype trees, information about historical recombinations in the population: A haplotype tree constructed at a given chromosomal location is an estimate of the genealogy of the haplotypes. TreeDT constructs these trees for all locations on the given haplotypes and performs a novel disequilibrium test on each tree: Is there a small set of subtrees with relatively high proportions of disease-associated chromosomes, suggesting shared genetic history for those and a likely disease gene location? We give a detailed description of TreeDT and the tree disequilibrium tests, we analyze the algorithm formally, and we evaluate its performance experimentally on both simulated and real data sets. Experimental results demonstrate that TreeDT has high accuracy on difficult mapping tasks and comparisons to other methods (EATDT, HPM, TDT) show that TreeDT is very competitive.
The problem of testing shared memories for memory coherence and consistency is studied. First, it is proved that detecting violations of coherence in an execution is NP-Complete, and it remains NP-Complete for a numbe...
详细信息
The problem of testing shared memories for memory coherence and consistency is studied. First, it is proved that detecting violations of coherence in an execution is NP-Complete, and it remains NP-Complete for a number of restricted instances. This result leads to a proof that all known consistency models are NP-Hard to verify. The complexity of verifying consistency models is not a mere consequence of coherence, and verifying sequential consistency remains NP-Complete even after coherence has been verified.
The purpose of this paper is to present a heuristic algorithm for the problem of workpieces scheduling in a Flexible Manufacturing Cell (FMC). The problem of workpieces scheduling in an FMC is to determine how and whe...
详细信息
ISBN:
(纸本)044481910X
The purpose of this paper is to present a heuristic algorithm for the problem of workpieces scheduling in a Flexible Manufacturing Cell (FMC). The problem of workpieces scheduling in an FMC is to determine how and when the workpieces could use the cell resources. The objective is to determine the set of starting times of each transport,done by the robot,of each workpiece to each operation which exploits the machine flexibility after identifing the dynamic bottleneck,while minimizing the makespan.
Given two partitions A and B of a totally ordered setS, of sizen, corresponding to the equivalence relationsRAandRBrespectively, the refinement problem calls for the computation of the partitionCcorresponding to the r...
详细信息
Given two partitions A and B of a totally ordered setS, of sizen, corresponding to the equivalence relationsRAandRBrespectively, the refinement problem calls for the computation of the partitionCcorresponding to the relationRAandRB. We present analgorithm for this problem. As an application, we present an algorithm that converts an inverted lists structure to a multiple attribute tree for a set of multi-dimensional points. Using the idea of the proposed algorithm we present an alternatealgorithm for an existing partition algorithm. The alternate algorithm is very simple to implement and direct to prove.
A variety of applications have motivated interest in the hidden-line and hidden-surface problem. This has resulted in a number of fundamentally different solutions. However no algorithm has been shown to be optimal. A...
详细信息
Bentley proposed a divide‐and‐conquer approach to solve the planar closest pair problem. In this paper, we shall show that the average case performance of this algorithm is proportional to the number of poins being ...
详细信息
Bentley proposed a divide‐and‐conquer approach to solve the planar closest pair problem. In this paper, we shall show that the average case performance of this algorithm is proportional to the number of poins being examined.
暂无评论