FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search
type: Item
instance of: scholarly article
title: FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search
zbMATH Open document ID: 1264.68222
DOI: 10.1155/2012/310328
author: Yuping Wang
author: Liang Bao
author: Yanni Li
published in: Mathematical Problems in Engineering
publication date: 2013-06-11T00:00:00Z
review text: Summary: Searching for the multiple longest common subsequences (MLCS) has significant applications in the areas of bioinformatics, information processing, and data mining, and so forth, Although a few parallel MLCS algorithms have been proposed, the efficiency and effectiveness of the algorithms are not satisfactory with the increasing complexity and size of biologic data. To overcome the shortcomings of the existing MLCS algorithms, and considering that MapReduce parallel framework of cloud computing being a promising technology for cost-effective high performance parallel computing, a novel finite automaton (FA) based on cloud computing called FACC is proposed under MapReduce parallel framework, so as to exploit a more efficient and effective general parallel MLCS algorithm. FACC adopts the ideas of matched pairs and finite automaton by preprocessing sequences, constructing successor tables, and common subsequences finite automaton to search for MLCS. Simulation experiments on a set of benchmarks from both real DNA and amino acid sequences have been conducted and the results show that the proposed FACC algorithm outperforms the current leading parallel MLCS algorithm FAST-MLCS.
Mathematics Subject Classification ID: 68W32
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68W10
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 6173177
Wikidata QID: Q58911416
describes a project that uses: MapReduce
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2012/310328
OpenAlex ID: W1965689044
cites work: Parallel processing of biological sequence comparison algorithms
cites work: The Complexity of Some Problems on Subsequences and Supersequences
cites work: The String-to-String Correction Problem
cites work: A linear space algorithm for computing maximal common subsequences
cites work: Bounds on the Complexity of the Longest Common Subsequence Problem
cites work: A fast algorithm for computing longest common subsequences
cites work: Enumerating longest increasing subsequences and patience sorting
cites work: A faster algorithm computing string edit distances
cites work: Efficient Parallel Algorithms for String Editing and Related Problems
cites work: Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
cites work: On computing the length of longest increasing subsequences
cites work: A fast algorithm for computing a longest common increasing subsequence
cites work: Faster Algorithms for Computing Longest Common Increasing Subsequences
Recommended article: The Longest Common Subsequence Problem A Finite Automata Approach
Recommended article: Efficient Longest Common Subsequence Computation Using Bulk-Synchronous Parallelism
Recommended article: Q4862293
Recommended article: A coarse-grained parallel algorithm for the all-substrings longest common subsequence problem
Recommended article: Q4607967
Recommended article: Q5289054
Recommended article: Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
Recommended article: A new efficient algorithm for computing the longest common subsequence
Recommended article: A New Efficient Algorithm for Computing the Longest Common Subsequence
description: scientific article; zbMATH DE number 6173177