A branch and bound algorithm for local multiple alignment.
A Branch and Bound Algorithm has been developed to find a set of window positions in a compilation of sequences with globally maximal information content. We have also developed an algorithm for brute force evaluation of solutions which is faster by a factor of the length of the windows than the naïve brute force algorithm. The combination of these two algorithms allows us to solve problems to optimality that were previously amenable only to heuristic algorithms.
Horton
P
P
Computer Science Division, University of California, Berkeley 94720, USA.
D000465:Algorithms; D000595:Amino Acid Sequence; D001426:Bacterial Proteins / Q000737:chemistry / Q000235:genetics; D001483:Base Sequence; D003198:Computer Simulation; D004247:DNA / Q000737:chemistry*; D004269:DNA, Bacterial / Q000737:chemistry / Q000235:genetics; D004926:Escherichia coli / Q000235:genetics; D011506:Proteins / Q000737:chemistry*; D016415:Sequence Alignment; D012697:Serine Endopeptidases / Q000737:chemistry / Q000235:genetics; D012984:Software; D000099160:LexA Repressor Protein
D001426:Bacterial Proteins; D004247:DNA; D004269:DNA, Bacterial; D011506:Proteins; D012697:Serine Endopeptidases; D000099160:LexA Repressor Protein