Bhandarkar Suchendra M, Huang Jinling, Arnold Jonathan
Department of Computer Science, The University of Georgia, Athens, Georgia 30602-7404, USA.
Proc IEEE Comput Soc Bioinform Conf. 2002;1:64-75.
Reconstructing a physical map of a chromosome from a genomic library presents a central computational problem in genetics. Physical map reconstruction in the presence of errors is a problem of high computational complexity. Parallel Monte Carlo methods for a maximum likelihood estimation-based approach to physical map reconstruction are presented. The estimation procedure entails gradient descent search for determining the optimal spacings between probes for a given probe ordering. The optimal probe ordering is determined using a simulated Monte Carlo algorithm. A two-tier parallelization strategy is proposed wherein the gradient descent search is parallelized at the lower level and the simulated Monte Carlo algorithm is simultaneously parallelized at the higher level. Implementation and experimental results on a network of shared-memory symmetric multiprocessors (SMPs) are presented.
从基因组文库重建染色体的物理图谱是遗传学中的一个核心计算问题。存在错误情况下的物理图谱重建是一个计算复杂度很高的问题。本文提出了基于最大似然估计的物理图谱重建方法的并行蒙特卡罗方法。估计过程需要进行梯度下降搜索，以确定给定探针排序下探针之间的最佳间距。使用模拟蒙特卡罗算法确定最佳探针排序。提出了一种两层并行化策略，其中梯度下降搜索在较低级别并行化，模拟蒙特卡罗算法在较高级别同时并行化。本文展示了在共享内存对称多处理器（SMP）网络上的实现和实验结果。
