FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search

DOI10.1155/2012/310328MaRDI QIDQ1954643zbMATH OpenOpenAlexWikidataFDO

Authors Yuping Wang, Liang Bao, Yanni Li

Publication date 11 June 2013

Published in Mathematical Problems in Engineering (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1155/2012/310328

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Parallel algorithms in computer science (68W10) Algorithms on strings (68W32) Analysis of algorithms (68W40)

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.

Recommendations

• The longest common subsequence problem -- a finite automata approach
• Efficient Longest Common Subsequence Computation Using Bulk-Synchronous Parallelism
• Publication:4862293
• A coarse-grained parallel algorithm for the all-substrings longest common subsequence problem
• Multivariate fine-grained complexity of longest common subsequence
• scientific article; zbMATH DE number 278833
• Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
• A new efficient algorithm for computing the longest common subsequence
• A New Efficient Algorithm for Computing the Longest Common Subsequence

Cites work

• A fast algorithm for computing a longest common increasing subsequence
• A fast algorithm for computing longest common subsequences
• A faster algorithm computing string edit distances
• A linear space algorithm for computing maximal common subsequences
• Bounds on the Complexity of the Longest Common Subsequence Problem
• Efficient Parallel Algorithms for String Editing and Related Problems
• Enumerating longest increasing subsequences and patience sorting
• Faster Algorithms for Computing Longest Common Increasing Subsequences
• Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
• On computing the length of longest increasing subsequences
• Parallel processing of biological sequence comparison algorithms
• The Complexity of Some Problems on Subsequences and Supersequences
• The String-to-String Correction Problem

Cited in

(1)

• A linear time complexity of breadth-first search using P system with membrane division

Describes a project that uses

Uses Software

• MapReduce

This page was built for publication: FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1954643)