Display Settings:

Format

Send to:

Choose Destination
See comment in PubMed Commons below
Pac Symp Biocomput. 2001:179-90.

An algorithm for statistical alignment of sequences related by a binary tree.

Author information

  • Department of Ecology and Genetics, University of Aarhus, Ny Munkegade, Aarhus, Denmark. jotun.hein@biology.au.dk

Abstract

An algorithm is presented that allows the calculation of the probability of a set of sequences related by a binary tree that has evolved according to the Thorne-Kishino-Felsenstein model (1991) for a fixed set of parameters. There are two ideas underlying this algorithm. Firstly, a markov chain is defined that generates ancestral sequences and their alignment at two neighboring nodes in a tree. Secondly, a stochastic walk on the binary tree, that defines a markov chain generating ancestral sequences and their alignment at the internal nodes in the tree is described. The running time of this algorithm is O(l2 kappa), where l is the geometric average of the sequence lengths and kappa the number of sequences--leaves at the binary tree. This could be improved to O(l kappa).

PMID:
11262938
[PubMed - indexed for MEDLINE]
PubMed Commons home

PubMed Commons

0 comments
How to join PubMed Commons

    Supplemental Content

    Loading ...
    Write to the Help Desk