Bioinformatics Vol. 19 no. 11 2003
Pages 1404-1411
© 2003 Oxford University Press
SATCHMO: sequence alignment and tree construction using hidden Markov models
1 195 Roque Moraes Drive, Mill Valley, CA 94941
2 Department of Bioengineering, University
of California, Berkeley, CA 94720, USA
Received on November 17, 2002
; revised on February 4, 2003
; accepted on February 7, 2003
Motivation:Aligning multiple proteins based on sequence information alone is challenging if sequence identity is low or there is a significant degree of structural divergence. We present a novel algorithm (SATCHMO) that is designed to address this challenge. SATCHMO simultaneously constructs a tree and a set of multiple sequence alignments, one for each internal node of the tree. The alignment at a given node contains all sequences within its sub-tree, and predicts which positions in those sequences are alignable and which are not. Aligned regions therefore typically get shorter on a path from a leaf to the root as sequences diverge in structure. Current methods either regard all positions as alignable (e.g. ClustalW), or align only those positions believed to be homologous across all sequences (e.g. profile HMM methods); by contrast SATCHMO makes different predictions of alignable regions in different subgroups. SATCHMO generates profile hidden Markov models at each node; these are used to determine branching order, to align sequences and to predict structurally alignable regions.
Results: In experiments on the BAliBASE benchmark alignment database, SATCHMO is shown to perform comparably to ClustalW and the UCSC SAM HMM software. Results using SATCHMO to identify protein domains are demonstrated on potassium channels, with implications for the mechanism by which tumor necrosis factor alpha affects potassium current.
Availability: The software is available for download from http://www.drive5.com/lobster/index.htm
Contact: bob{at}drive5.com
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  N. Fernandez-Fuentes, B. K. Rai, C. J. Madrid-Aliste, J. Eduardo Fajardo, and A. Fiser Comparative protein structure modeling by combining multiple templates and optimizing sequence-to-structure alignments Bioinformatics, October 1, 2007; 23(19): 2558 - 2565. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J. G. Glanville, D. Kirshner, N. Krishnamurthy, and K. Sjolander Berkeley Phylogenomics Group web servers: resources for structural phylogenomic analysis Nucleic Acids Res., July 13, 2007; 35(suppl_2): W27 - W32. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. M. Phuong, C. B. Do, R. C. Edgar, and S. Batzoglou Multiple alignment of protein sequences with repeats and rearrangements Nucleic Acids Res., November 6, 2006; 34(20): 5932 - 5942. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. Cheng and P. Baldi A machine learning information retrieval approach to protein fold recognition Bioinformatics, June 15, 2006; 22(12): 1456 - 1463. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
H. Zhou and Y. Zhou SPEM: improving multiple sequence alignment with sequence profiles and predicted secondary structures Bioinformatics, September 15, 2005; 21(18): 3615 - 3621. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 L. K. Fritz-Laylin, N. Krishnamurthy, M. Tor, K. V. Sjolander, and J. D.G. Jones Phylogenomic Analysis of the Receptor-Like Proteins of Rice and Arabidopsis Plant Physiology, June 1, 2005; 138(2): 611 - 623. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. Soding Protein homology detection by HMM-HMM comparison Bioinformatics, April 1, 2005; 21(7): 951 - 960. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 H.-Y. Lee, Y. Xu, Y. Huang, A. H. Ahn, G. W.J. Auburger, M. Pandolfo, H. Kwiecinski, D. A. Grimes, A. E. Lang, J. E. Nielsen, et al. The gene for paroxysmal non-kinesigenic dyskinesia encodes an enzyme in a stress response pathway Hum. Mol. Genet., December 15, 2004; 13(24): 3161 - 3170. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 H. Viklund and A. Elofsson Best {alpha}-helical transmembrane protein topology predictions are achieved using hidden Markov models and evolutionary information Protein Sci., July 1, 2004; 13(7): 1908 - 1917. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. A. Marti-Renom, M.S. Madhusudhan, and A. Sali Alignment of protein sequences by their profiles Protein Sci., April 1, 2004; 13(4): 1071 - 1087. [Abstract] [Full Text] [PDF]
|
|