.png){kind=icon}
返回
Parallel progressive multiple sequence alignment on reconfigurable meshes
.png){kind=icon}
OA
AI
DOI：10.1186/1471-2164-12-S5-S4.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Background: One of the most fundamental and challenging tasks in bio-informatics is to identify related sequences and their hidden biological significance. The most popular and proven best practice method to accomplish this task is aligning multiple sequences together. However, multiple sequence alignment is a computing extensive task. In addition, the advancement in DNA/RNA and Protein sequencing techniques has created a vast amount of sequences to be analyzed that exceeding the capability of traditional computing models. Therefore, an effective parallel multiple sequence alignment model capable of resolving these issues is in a great demand. Results: We design O(1) run-time solutions for both local and global dynamic programming pair-wise alignment algorithms on reconfigurable mesh computing model. To align m sequences with max length n, we combining the parallel pair-wise dynamic programming solutions with newly designed parallel components. We successfully reduce the progressive multiple sequence alignment algorithm's run-time complexity from O(m x n(4)) to O(m) using O(m x n(3)) processing units for scoring schemes that use three distinct values for match/mismatch/gapextension. The general solution to multiple sequence alignment algorithm takes O(m x n(4)) processing units and completes in O(m) time. Conclusions: To our knowledge, this is the first time the progressive multiple sequence alignment algorithm is completely parallelized with O(m) run-time. We also provide a new parallel algorithm for the Longest Common Subsequence (LCS) with O(1) run-time using O(n(3)) processing units. This is a big improvement over the current best constant-time algorithm that uses O(n(4)) processing units.
Keyword:
ALGORITHM
SEARCH
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
3.7
论文数:
1.9W
被引数:
5.2W
机构
引用论文
.png){kind=icon}
Characterization of polymer matrix and low melting point solder for anisotropic conductive film各向异性导电膜用聚合物基体及低熔点焊料的表征
PREAI
分享收藏
分享收藏
查看更多内容