Elsevier

Methods in Enzymology

Volume 183, 1990, Pages 626-645
Methods in Enzymology

[39] Unified approach to alignment and phylogenies

https://doi.org/10.1016/0076-6879(90)83041-7Get rights and content

Publisher Summary

Two important considerations in the analysis of molecular sequences are alignment and phylogeny reconstruction. Typically, the procedure to find the phylogeny would presume an alignment of all sequences obtained manually. Each column would be treated independently and then be explained by a series of substitutions. Different branching configurations or tree topologies would be checked, and the one allowing for shortest total branch length would be chosen. The traditional dynamic programming algorithm can be generalized to compare sequence graphs and to find sequence subgraphs that are close to each other according to some sequence metric. Simultaneously, the subgraphs are aligned. The most informative distances for the tree construction process are calculated. When the method is applied to larger sequence numbers the complete distance matrix is not calculated because it is wasteful. Rearrangements are performed on the obtained tree to improve the overall fit of the tree to the distance data. The resulting tree is used to guide the alignment algorithm such that a parsimony tree is obtained that has the same topology as the distance tree. It is at this point that the graph comparison algorithm is used.

References (22)

  • L.R. Foulds et al.

    Adv. Appl. Math.

    (1982)
  • P. Sellers

    J. Comb. Theor.

    (1974)
  • W.H.E. Day

    Bull. Math. Biol.

    (1984)
  • E. Ukkonen

    Inf. Control

    (1985)
  • D.F. Robinson

    J. Comb. Theor.

    (1971)
  • M.O. Dayhoff
  • R.F. Doolittle

    Of ORFs and URFs

    (1986)
  • D. Sankoff

    SIAM J Appl. Math.

    (1975)
  • J. J. Hein, J. Theor. Biol. (submitted for...
  • O. Gotoh

    J. Mol. Biol.

    (1981)
  • D. Sankoff

    Time Warps, String Edits and Macromolecules

  • Cited by (374)

    • Up-regulation of neutrophil activating protein in Helicobacter pylori under high-salt stress: Structural and phylogenetic comparison with bacterial iron-binding ferritins

      2013, Biochimie
      Citation Excerpt :

      The alignment, phylogenetic analysis, and estimation of sequence divergence were carried out by using MEGALIGN and PROTEAN programs (DNASTAR, Madison, WI). A phylogenetic tree was constructed based on the percent divergence between protein sequences using a combination of distance matrix and approximate parsimony methods in the phylogeny generation program of Hein [36]. The tree was built using the CLUSTAL V program and weighted residue-weight table.

    • Alignment of, and phylogenetic inference from, random sequences: The susceptibility of alternative alignment methods to creating artifactual resolution and support

      2010, Molecular Phylogenetics and Evolution
      Citation Excerpt :

      This approach has variously been described as using a “hodgepodge of criteria” (Ogden and Whiting, 2003, p. 441), being used “mainly due to tradition” (Giribet, 2005, p. 396), “inappropriate for the reconstruction of phylogeny” (Mindell, 1991a, p. 78), or even being “fundamentally flawed” (Lunter et al., 2005, p. 2). Furthermore, it has been asserted that simultaneous alignment assumes a “star” phylogeny wherein all sequences are equally related to one another (Hein, 1990; Mindell, 1991a). In contrast, we suggest that simultaneous alignment using the similarity criterion followed by tree search simply avoids biasing the results in favor of any particular tree topology.

    • Approximation algorithms for constrained generalized tree alignment problem

      2009, Discrete Applied Mathematics
      Citation Excerpt :

      Wang and Gusfield [14,17,18] presented an improved version of 2-approximation algorithm and the polynomial-time approximation scheme. From the perspective of heuristics, Sankoff [12], Kruskal and Sankoff [11] and Altschul and Lipman [1], proposed iterative methods for tree alignment, Hein [7,8] introduced an approach for tree alignment based on the concept of sequence graph. For an excellent overview of algorithms for tree alignment and related problems, we refer the reader to Gusfield [6], and Wang and Jiang [16].

    View all citing articles on Scopus
    View full text