A space-efficient algorithm for three sequence alignment and ancestor inference

Feng Yue, Jijun Tang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


We propose a novel algorithm to simultaneously align three biological sequences with affine gap model and infer their common ancestral sequence. It applies the divide-and-conquer strategy to reduce the memory usage from O(n3) to O(n2). At the same time, it is based on dynamic programming and thus the optimal alignment is guaranteed. We implemented the algorithm and tested it extensively with both BAliBASE dataset and simulation data generated by Random Model of Sequence Evolution (ROSE). Compared with other popular multiple sequence alignment tools such as ClustalW and T-Coffee, our program produces not only better alignment, but also better ancestral sequence.

Original languageEnglish (US)
Pages (from-to)192-204
Number of pages13
JournalInternational Journal of Data Mining and Bioinformatics
Issue number2
StatePublished - 2009


  • Bioinformatics
  • Data mining
  • Median sequence
  • Phylgogeny reconstruction
  • Three sequences alignment
  • Tree alignment

ASJC Scopus subject areas

  • Information Systems
  • Biochemistry, Genetics and Molecular Biology(all)
  • Library and Information Sciences


Dive into the research topics of 'A space-efficient algorithm for three sequence alignment and ancestor inference'. Together they form a unique fingerprint.

Cite this