Algorithms for Colinear Chaining with Overlaps and Gap Costs

Journal of computational biology: A journal of computational molecular cell biology

article

Chirag Jain¹  Daniel Gibney²  Sharma V. Thankachan³ 

[1] Department of Computational and Data Sciences, Indian Institute of Science;School of Computational Science and Engineering, Georgia Institute of Technology Atlanta;Department of Computer Science, University of Central Florida

关键词: alignment;    colinear chaining;    edit distance;   

DOI  :  10.1089/cmb.2022.0266

学科分类：生物科学（综合）

来源: Mary Ann Liebert, Inc. Publishers

【 摘 要 】

Colinear chaining has proven to be a powerful heuristic for finding near-optimal alignments of long DNA sequences (e.g., long reads or a genome assembly) to a reference. It is used as an intermediate step in several alignment tools that employ a seed-chain-extend strategy. Despite this popularity, efficient subquadratic time algorithms for the general case where chains support anchor overlaps and gap costs are not currently known. We present algorithms to solve the colinear chaining problem with anchor overlaps and gap costs in time, wheren0.9 with edit distance for closely as well as distantly related sequences.

【 授权许可】

Unknown