title: HAlign: Fast multiple similar DNA/RNA sequence alignment based on the centre star strategy.
abstract: BACKGROUND
  Multiple sequence alignment (MSA) is important work, but bottlenecks arise in the massive MSA of homologous DNA or genome sequences. Most of the available state-of-the-art software tools cannot address large-scale datasets, or they run rather slowly. The similarity of homologous DNA sequences is often ignored. Lack of parallelization is still a challenge for MSA research.
  
  
  RESULTS
  We developed two software tools to address the DNA MSA problem. The first employed trie trees to accelerate the centre star MSA strategy. The expected time complexity was decreased to linear time from square time. To address large-scale data, parallelism was applied using the hadoop platform. Experiments demonstrated the performance of our proposed methods, including their running time, sum-of-pairs scores and scalability. Moreover, we supplied two massive DNA/RNA MSA datasets for further testing and research.
authors: School of Computer Science and Technology, Tianjin University, Tianjin, China, State Key Laboratory of System Bioengineering of the Ministry of Education, Tianjin University, Tianjin, China and.
authors: Quan
authors: Q
authors: Zou
authors: School of Computer Science and Technology, Tianjin University, Tianjin, China, School of Computer Science and Technology, Harbin Institute of Technology, Harbin, China.
authors: Qinghua
authors: Q
authors: Hu
authors: School of Computer Science and Technology, Harbin Institute of Technology, Harbin, China.
authors: Maozu
authors: M
authors: Guo
authors: School of Computer Science and Technology, Harbin Institute of Technology, Harbin, China.
authors: Guohua
authors: G
authors: Wang
mesh_terms: D000465:Algorithms; D006801:Humans; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D017423:Sequence Analysis, RNA / Q000379:methods*; D012984:Software