A Caltech Library Service

Picking Alignments from (Steiner) Trees

Lam, Fumei and Alexandersson, Marina and Pachter, Lior (2003) Picking Alignments from (Steiner) Trees. Journal of Computational Biology, 10 (3-4). pp. 509-520. ISSN 1066-5277. doi:10.1089/10665270360688156.

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 nonconserved 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, succesfully reducing the Viterbi algorithm search space of alignment PHMMs by three orders of magnitude.

Item Type:Article
Related URLs:
URLURL TypeDescription
Pachter, Lior0000-0002-9164-6231
Additional Information:© 2003 Mary Ann Liebert, Inc. M.A. was partially supported by STINT, the Swedish Foundation for International Cooperation in Research and Higher Education, and the Center for Pure and Applied Mathematics at U.C. Berkeley. 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
University of California, BerkeleyUNSPECIFIED
Subject Keywords:alignment, Steiner tree, hidden Markov model
Issue or Number:3-4
Record Number:CaltechAUTHORS:20170308-153301235
Persistent URL:
Official Citation:Fumei Lam, Marina Alexandersson, and Lior Pachter. Journal of Computational Biology. July 2003, 10(3-4): 509-520. doi:10.1089/10665270360688156.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:74936
Deposited By: George Porter
Deposited On:09 Mar 2017 15:45
Last Modified:15 Nov 2021 16:29

Repository Staff Only: item control page