A STUDY OF MASSIVELY PARALLEL SIMULATED ANNEALING ALGORITHMS FOR CHROMOSOME RECONSTRUCTION VIA CLONE ORDERING
作者:
SUCHENDRAM. BHANDARKAR,
SRIDHAR CHIRRAVURI,
期刊:
Parallel Algorithms and Applications
(Taylor Available online 1996)
卷期:
Volume 9,
issue 1-2
页码: 67-89
ISSN:1063-7192
年代: 1996
DOI:10.1080/10637199608915564
出版商: Taylor & Francis Group
关键词: Simulated annealing;massively parallel processing;chromosome reconstruction;clone ordering;F.2.2;J.3
数据来源: Taylor
摘要:
Ordering clones from a genomic library into physical maps of whole chromosomes presents a central computational problem in genetics. Chromosome reconstruction via clone ordering is shown to be isomorphic to the NP-completeOptimal Linear Orderingproblem. Massively parallel algorithms for simulated annealing based on Markov chain distribution are proposed and applied to the problem of chromosome reconstruction via clone ordering. Perturbation methods and problem-specific annealing heuristics arc proposed and described. These algorithms are implemented on a 2048 processor MasPar MP-2 system which is an SIMD 2-D toroidal mesh architecture. Convergence, speedup and scalability characteristics of the various algorithms are analyzed and discussed. Results indicate that for an optimal clone ordering, a single Markov chain of solution states should not be distributed across more than two adjoining processing elements (PE's) on the MasPar MP-2.
点击下载:
PDF (421KB)
返 回