Open AccessA fast and memory efficient MLCS algorithm by character merging for DNA sequences alignment
Author(s) -
Sen Liu,
Yuping Wang,
Wuning Tong,
Shiwei Wei
Publication year - 2019
Publication title -
bioinformatics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.599
H-Index - 390
eISSN - 1367-4811
pISSN - 1367-4803
DOI - 10.1093/bioinformatics/btz725
Subject(s) - computer science , algorithm , character (mathematics) , subsequence , longest common subsequence problem , dynamic programming , directed acyclic graph , state (computer science) , sequence (biology) , longest increasing subsequence , smith–waterman algorithm , time complexity , construct (python library) , sequence alignment , mathematics , biology , genetics , mathematical analysis , peptide sequence , programming language , bounded function , gene , geometry
Multiple longest common subsequence (MLCS) problem is searching all longest common subsequences of multiple character sequences. It appears in many fields such as data mining, DNA alignment, bioinformatics, text editing and so on. With the increasing in sequence length and number of sequences, the existing dynamic programming algorithms and the dominant point-based algorithms become ineffective and inefficient, especially for large-scale MLCS problems.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom