title: TreeRefiner: a tool for refining a multiple alignment on a phylogenetic tree.
abstract: We present TreeRefiner, a tool for refining multiple alignments of biological sequences. Given a multiple alignment, a phylogenetic tree, and scoring parameters as input, TreeRefiner optimizes the sum-of-pairs function in a restricted three-dimensional space around the alignment. At each internal node of the unrooted tree, the multiple alignment is projected to the sub-alignments corresponding to the three neighboring nodes, and three-dimensional dynamic programming is performed within a user-specified radius r around the original alignment. We test TreeRefiner on simulated sequences aligned by several popular tools, and demonstrate substantial improvements in the percentage of correctly aligned positions.
authors.affiliation: Department of Computer Science, Stanford University, CA 94305, USA. amanohar@cs.stanford.edu
authors.forename: Aswath
authors.initials: A
authors.lastname: Manohar
authors.forename: Serafim
authors.initials: S
authors.lastname: Batzoglou
mesh_terms: D000465:Algorithms; D000818:Animals; D001483:Base Sequence; D002874:Chromosome Mapping / Q000379:methods*; D006801:Humans; D008969:Molecular Sequence Data; D010802:Phylogeny; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software