A Caltech Library Service

Picking alignments from (Steiner) trees

Pachter, Lior and Lam, Fumei and Alexandersson, Marina (2002) Picking alignments from (Steiner) trees. In: Proceedings of the sixth annual international conference on Computational biology (RECOMB '02). ACM , New York, NY, pp. 246-253. ISBN 1-58113-498-3.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


The application of Needleman-Wunsch alignment techniques to biological sequences is complicated by two serious problems when the sequences are long: the running time, which scales as the product of the lengths of sequences, and the difficulty in obtaining suitable parameters that produce meaningful alignments. The running time problem is often corrected by reducing the search space, using techniques such as banding, or chaining of high scoring pairs. The parameter problem is more difficult to fix, partly because the probabilistic model, which Needleman-Wunsch is equivalent to, does not capture a key feature of biological sequence alignments, namely the alternation of conserved blocks and seemingly unrelated non-conserved segments. We present a solution to the problem of designing efficient search spaces for pair hidden Markov models that align biological sequences by taking advantage of their associated features. Our approach leads to an optimization problem, for which we obtain a 2-approximation algorithm, and that is based on the construction of Manhattan networks, which are close relatives of Steiner trees. We describe the underlying theory and show how our methods can be applied to alignment of DNA sequences in practice, successfully reducing the Viterbi algorithm search space of alignment PHMMs by three orders of magnitude.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Pachter, Lior0000-0002-9164-6231
Additional Information:© 2002 ACM. M. A. was partially supported by STINT, the Swedish Foundation for International Cooperation in Research and Higher Education. Thanks to Nick Bray for helping with some of the implementation of SLIM and to Simon Cawley for helpful discussions and suggestions.
Funding AgencyGrant Number
Swedish Foundation for International Cooperation in Research and Higher Education (STINT)UNSPECIFIED
Record Number:CaltechAUTHORS:20170309-094423019
Persistent URL:
Official Citation:Lior Pachter and Fumei Lam. 2002. Picking alignments from (steiner) trees. In Proceedings of the sixth annual international conference on Computational biology (RECOMB '02), Gene Myers, Sridhar Hannenhalli, David Sankoff, Sorin Istrail, Pavel Pevzner, and Michael Waterman (Eds.). ACM, New York, NY, USA, 246-253. DOI:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:74970
Deposited By: George Porter
Deposited On:13 Mar 2017 15:13
Last Modified:15 Nov 2021 16:29

Repository Staff Only: item control page