%0 Journal Article
%T Parallel Algorithms for Reversal Distance of Permutations on PRAM and LARPBS<br>PRAM和LARPBS模型上有向序列翻转距离并行算法
%A SHEN Yi-Fei
%A CHEN Guo-Liang
%A ZHANG Qiang-Feng
%A <br>沈一飞
%A 陈国良
%A 张强锋
%J 软件学报
%D 2007
%I 
%X This paper presents two parallel algorithms to compute reversal distance of two signed permutations on different models. These two algorithms are based on Hannenhalli and Pevzner's theory and composed of three key steps: Construct break point graph, compute the number of cycles in break point graph and compute the number of hurdles in break point graph. The first algorithm runs in O(log2n) time using O(n2) processors in SIMD-CREW model. The second one can solve the problem in O(logn) bus cycles by using O(n3) processors on the linear array with a reconfigurable pipelined bus system (LARPBS).
%K parallel algorithm
%K optical bus parallel model
%K reversal distance
%K genome rearrangements
%K sequence comparison
%K CREW-PRAM model<br>并行算法
%K 光总线并行模型
%K 反转距离
%K 基因组重排
%K 序列比较
%K CREW-PRAM模型
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=DFF7679BE7012A7531F14147B7648217&yid=A732AF04DDA03BB3&vid=13553B2D12F347E8&iid=708DD6B15D2464E8&sid=40E8FEA07A3DBDC3&eid=5B0AFEF9BB2761AD&journal_id=1000-9825&journal_name=软件学报&referenced_num=0&reference_num=13