Efficient implied alignment

作     者：Washburn, Alex J. Wheeler, Ward C. 

作者机构：Amer Museum Nat Hist Div Invertebrate Zool 200 Cent Pk West New York NY 10024 USA 

出 版 物：《BMC BIOINFORMATICS》 (英国医学委员会:生物信息)

年 卷 期：2020年第21卷第1期

页      面：296-296页

核心收录：

学科分类：0710[理学-生物学] 0836[工学-生物工程] 10[医学] 

基　　金：DARPA SIMPLEX ("Integrating Linguistic, Ethnographic, and Genetic Information of Human Populations: Databases and Tools") [DARPA-BAA-14-59 SIMPLEX TA-2] Robert J. Kleberg Jr. and Helen C. Kleberg foundation grant "Mechanistic Analyses of Pancreatic Cancer Evolution" 

主　　题：Dynamic homology Implied alignment Multiple string alignment Phylogenetics Sequence alignment Tree alignment 

摘      要：Background: Given a binary tree T of n leaves, each leaf labeled by a string of length at most k, and a binary string alignment function circle times, an implied alignment can be generated to describe the alignment of a dynamic homology for T. This is done by first decorating each node of T with an alignment context using circle times, in a post-order traversal, then, during a subsequent pre-order traversal, inferring on which edges insertion and deletion events occurred using those internal node decorations. Results: Previous descriptions of the implied alignment algorithm suggest a technique of back-propagation with time complexity O (k(2) * n(2)). Here we describe an implied alignment algorithm with complexity O (k * n(2)). For well-behaved data, such as molecular sequences, the runtime approaches the best-case complexity of Omega(k * n). Conclusions: The reduction in the time complexity of the algorithm dramatically improves both its utility in generating multiple sequence alignments and its heuristic utility.