@inproceedings{bdd9934eda05499684203bb848425deb,

title = "The maximum weight trace problem in multiple sequence alignment",

abstract = "We define a new problem in multiple sequence alignment, called maximum weight trace. The problem formalizes in a natural way the common practice of merging pairwise alignments to form multiple sequence alignments, and contains a version of the minimum sum of pairs alignment problem as a special case. Informally, the input is a set of pairs of matched characters from the sequences; each pair has an associated weight. The output is a subset of the pairs of maximum total weight that satisfies the following property: there is a multiple alignment that places each pair of characters selected by the subset together in the same column. A set of pairs with this property is called a trace. Intuitively a trace of maximum weight specifies a multiple alignment that agrees as much as possible with the character matches of the input. We develop a branch and bound algorithm for maximum weight trace. Though the problem is NP-complete, an implementation of the algorithm shows we can solve instances on as many as 6 sequences of length 250 in a few minutes. These are among the largest instances that have been solved to optimality to date for any formulation of multiple sequence alignment.",

author = "John Kececioglu",

note = "Funding Information: We thank Dr. David Lipman for the protein sequences of Figure 6. This research was supported by a postdoctoral fellowship from the Program in Mathematics and Molecular Biology of the University of California at Berkeley under NSF Grant DMS-8720208. Author?s electronic mail address: kece@cs.ucdavis.edu. Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1993.; Conference of the European Society for Fuzzy Logic and Technology, EUSFLAT 2017 and 16th International Workshop on Intuitionistic Fuzzy Sets and Generalized Nets, IWIFSGN 2017 ; Conference date: 11-09-2017 Through 15-09-2017",

year = "1993",

doi = "10.1007/bfb0029800",

language = "English (US)",

isbn = "9783540567646",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "106--119",

editor = "Alberto Apostolico and Alberto Apostolico and {Crochemore }, Maxime and Zvi Galil and Zvi Galil and Udi Manber",

booktitle = "Combinatorial Pattern Matching - 4th Annual Symposium, CPM 1993, Proceedings",

}