A Divide and Conquer Approach to Multiple Alignment

Dress A, Füllen G, Perrey S (1995)
In: Proceedings of the Third International Conference on Intelligent Systems for Molecular Biology. Rawlings C, Clark D, Altman R, Hunter L, Lengauer T, Wodak S (Eds); Menlo Park: AAAI Press .

Konferenzbeitrag | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Dress, AndreasUniBi; Füllen, Georg; Perrey, Sören
Herausgeber*in
Rawlings, Christopher ; Clark, Dominic ; Altman, Russ ; Hunter, Lawrence ; Lengauer, Thomas ; Wodak, Shoshana
Abstract / Bemerkung
We present a report on work in progress on a divide and conquer approach to multiple alignment. The algorithm makes use of the costs calculated from applying the standard dynamic programming scheme to all pairs of sequences. The resulting cost matrices for pairwise alignment give rise to secondary matrices containing the additional costs imposed by fixing the path through the dynamic programming graph at a particular vertex. Such a constraint corresponds to a division of the problem obtained by slicing both sequences between two particular positions, and aligning the two sequences on the left and the two sequences on the right, charging for gaps introduced at the slicing point. To obtain an estimate for the additional cost imposed by forcing the multiple alignment through a particular vertex in the whole hypercube, we will take a (weighted) sum of secondary costs over all pairwise projections of the division of the problem, as defined by this vertex, that is, by slicing all sequences at the points suggested by the vertex. We then use that partition of every single sequence under consideration into two 'halfs' which imposes a minimal (weighted) sum of pairwise additional costs, making sure that one of the sequences is divided somewhere close to its midpoint. Hence, each iteration can cut the problem size in half. As the enumeration of all possible partitions may restrict this approach to small-size problems, we eliminate futile partitions, and organize their enumeration in a way that starts with the most promising ones.(ABSTRACT TRUNCATED AT 250 WORDS)
Erscheinungsjahr
1995
Titel des Konferenzbandes
Proceedings of the Third International Conference on Intelligent Systems for Molecular Biology
Konferenz
Third International Conference on Intelligent Systems for Molecular Biology (ISMB-95)
Konferenzort
Robinson College, Cambridge, United Kingdom
Konferenzdatum
1995-07-16 – 1995-07-19
ISBN
978-0-929280-83-7
Page URI
https://pub.uni-bielefeld.de/record/1668170

Zitieren

Dress A, Füllen G, Perrey S. A Divide and Conquer Approach to Multiple Alignment. In: Rawlings C, Clark D, Altman R, Hunter L, Lengauer T, Wodak S, eds. Proceedings of the Third International Conference on Intelligent Systems for Molecular Biology. Menlo Park: AAAI Press ; 1995.
Dress, A., Füllen, G., & Perrey, S. (1995). A Divide and Conquer Approach to Multiple Alignment. In C. Rawlings, D. Clark, R. Altman, L. Hunter, T. Lengauer, & S. Wodak (Eds.), Proceedings of the Third International Conference on Intelligent Systems for Molecular Biology Menlo Park: AAAI Press .
Dress, A., Füllen, G., and Perrey, S. (1995). “A Divide and Conquer Approach to Multiple Alignment” in Proceedings of the Third International Conference on Intelligent Systems for Molecular Biology, Rawlings, C., Clark, D., Altman, R., Hunter, L., Lengauer, T., and Wodak, S. eds. (Menlo Park: AAAI Press ).
Dress, A., Füllen, G., & Perrey, S., 1995. A Divide and Conquer Approach to Multiple Alignment. In C. Rawlings, et al., eds. Proceedings of the Third International Conference on Intelligent Systems for Molecular Biology. Menlo Park: AAAI Press .
A. Dress, G. Füllen, and S. Perrey, “A Divide and Conquer Approach to Multiple Alignment”, Proceedings of the Third International Conference on Intelligent Systems for Molecular Biology, C. Rawlings, et al., eds., Menlo Park: AAAI Press , 1995.
Dress, A., Füllen, G., Perrey, S.: A Divide and Conquer Approach to Multiple Alignment. In: Rawlings, C., Clark, D., Altman, R., Hunter, L., Lengauer, T., and Wodak, S. (eds.) Proceedings of the Third International Conference on Intelligent Systems for Molecular Biology. AAAI Press , Menlo Park (1995).
Dress, Andreas, Füllen, Georg, and Perrey, Sören. “A Divide and Conquer Approach to Multiple Alignment”. Proceedings of the Third International Conference on Intelligent Systems for Molecular Biology. Ed. Christopher Rawlings, Dominic Clark, Russ Altman, Lawrence Hunter, Thomas Lengauer, and Shoshana Wodak. Menlo Park: AAAI Press , 1995.

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Quellen

PMID: 7584425
PubMed | Europe PMC

Suchen in

Google Scholar
ISBN Suche