@inproceedings{83b9467907944515bed3676c431d32af,
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:
[email protected]. 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 Maxime Crochemore and Zvi Galil and Udi Manber",
booktitle = "Combinatorial Pattern Matching - 4th Annual Symposium, CPM 1993, Proceedings",
}