PubMed · 9672828
Alignments without low-scoring regions.
Abstract
Given a strong match between regions of two sequences, how far can the match be meaningfully extended if gaps are allowed in the resulting alignment? The aim is to avoid searching beyond the point that a useful extension of the alignment is likely to be found. Without loss of generality, we can restrict attention to the suffixes of the sequences that follow the strong match, which leads to the following formal problem. Given two sequences and a fixed X > 0, align initial portions of the sequences subject to the constraint that no section of the alignment scores below -X. Our results indicate that computing an optimal alignment under this constraint is very expensive. However, less rigorous conditions on the alignment can be guaranteed by quite efficient algorithms. One of these variants has been implemented in a new release of the Blast suite of database search programs.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
Z Zhang, P Berman, W Miller. 1998. Alignments without low-scoring regions.. https://doi.org/10.1089/cmb.1998.5.197. https://pubmed.health/record/pubmed%3A9672828/alignments-without-low-scoring-regions
Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite PubMed Health by Indiciae: BibTeX · RIS.