A branch and bound algorithm for local multiple alignment.

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)368-383
Number of pages16
JournalPacific Symposium on Biocomputing. Pacific Symposium on Biocomputing
Publication statusPublished - 1996 Jan 1

Fingerprint

Heuristics

All Science Journal Classification (ASJC) codes

  • Medicine(all)

Cite this

@article{c0612fdbccd8467ba7187ffec879ed3a,
title = "A branch and bound algorithm for local multiple alignment.",
abstract = "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{\"i}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.",
author = "Paul, {Brice Horton Ii}",
year = "1996",
month = "1",
day = "1",
language = "English",
pages = "368--383",
journal = "Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing",
issn = "2335-6936",

}

TY - JOUR

T1 - A branch and bound algorithm for local multiple alignment.

AU - Paul, Brice Horton Ii

PY - 1996/1/1

Y1 - 1996/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0030309358&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030309358&partnerID=8YFLogxK

M3 - Article

SP - 368

EP - 383

JO - Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing

JF - Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing

SN - 2335-6936

ER -