Tsukuba BB: A branch and bound algorithm for local multiple sequence alignment

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)


In this paper we present a branch and bound algorithm for local gapless multiple sequence alignment (motif alignment) and its implementation. This is the first program to exploit the fact that the motif alignment problem is easier for short motifs. Indeed for a fixed motif width the running time of the algorithm is asymptotically linear in the size of the input. We tested the performance of the program on a dataset of 300 E.coli promoter sequences. For a motif width of 4 the optimal alignment of the entire set of sequences can be found. For the more natural motif width of 6 the program can align 19 sequences of length 100; more than twice the number of sequences which can be aligned by the best previous exact algorithm. The algorithm can relax the constraint of requiring each sequence to be aligned, and align 100 of the 300 promoter sequences with a motif width of 6. We also compare the effectiveness of the Gibbs sampling and beam search heuristics on this problem and show that in some cases our branch and bound algorithm can find the optimal solution, with proof of optimality, when those heuristics fail to find the optimal solution.

Original languageEnglish
Title of host publicationCombinatorial Pattern Matching - 11th Annual Symposium, CPM 2000, Proceedings
EditorsDavid Sankoff, Raffaele Giancarlo
PublisherSpringer Verlag
Number of pages15
ISBN (Electronic)3540676333, 9783540676331
Publication statusPublished - 2000 Jan 1
Event11th Annual Symposium on Combinatorial Pattern Matching, CPM 2000 - Montreal, Canada
Duration: 2000 Jun 212000 Jun 23

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other11th Annual Symposium on Combinatorial Pattern Matching, CPM 2000

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Tsukuba BB: A branch and bound algorithm for local multiple sequence alignment'. Together they form a unique fingerprint.

Cite this