Limits...
BitPAl: a bit-parallel, general integer-scoring sequence alignment algorithm.

Loving J, Hernandez Y, Benson G - Bioinformatics (2014)

Bottom Line: Bit-parallelism has been successfully applied to the longest common subsequence (LCS) and edit-distance problems, producing fast algorithms in practice.We have developed BitPAl, a bit-parallel algorithm for general, integer-scoring global alignment.In timed tests, we show that BitPAl runs 7-25 times faster than a standard iterative algorithm.

View Article: PubMed Central - PubMed

Affiliation: Laboratory for Biocomputing and Informatics, Graduate Program in Bioinformatics, and Department of Computer Science, Boston University, Boston, MA 02215, USA Laboratory for Biocomputing and Informatics, Graduate Program in Bioinformatics, and Department of Computer Science, Boston University, Boston, MA 02215, USA.

Show MeSH

Related in: MedlinePlus

Relative size of Zones as I (mismatch penalty) decreases from 2G (twice gap penalty) where there is no preference for mismatches, to zero, where mismatches are free and gaps are introduced only to obtain matches
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4221118&req=5

btu507-F2: Relative size of Zones as I (mismatch penalty) decreases from 2G (twice gap penalty) where there is no preference for mismatches, to zero, where mismatches are free and gaps are introduced only to obtain matches

Mentions: The recursion for ΔV is summarized in the Function Table in Figure 1. Note the value I − G, which frequently occurs in the recursion, and the relation . They set the boundaries for the marked zones in the table. These zones comprise () pairs, which determine how the best score of a cell in S is obtained in the absence of a match, either as an indel from the left (Zones A and B), a mismatch (Zone C) or an indel from above (Zone D). Borders between zones, indicated by dotted lines, yield ties for the best score. Figure 2 shows how the relative size of the Zones changes with changes in I and G.Fig. 1.


BitPAl: a bit-parallel, general integer-scoring sequence alignment algorithm.

Loving J, Hernandez Y, Benson G - Bioinformatics (2014)

Relative size of Zones as I (mismatch penalty) decreases from 2G (twice gap penalty) where there is no preference for mismatches, to zero, where mismatches are free and gaps are introduced only to obtain matches
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4221118&req=5

btu507-F2: Relative size of Zones as I (mismatch penalty) decreases from 2G (twice gap penalty) where there is no preference for mismatches, to zero, where mismatches are free and gaps are introduced only to obtain matches
Mentions: The recursion for ΔV is summarized in the Function Table in Figure 1. Note the value I − G, which frequently occurs in the recursion, and the relation . They set the boundaries for the marked zones in the table. These zones comprise () pairs, which determine how the best score of a cell in S is obtained in the absence of a match, either as an indel from the left (Zones A and B), a mismatch (Zone C) or an indel from above (Zone D). Borders between zones, indicated by dotted lines, yield ties for the best score. Figure 2 shows how the relative size of the Zones changes with changes in I and G.Fig. 1.

Bottom Line: Bit-parallelism has been successfully applied to the longest common subsequence (LCS) and edit-distance problems, producing fast algorithms in practice.We have developed BitPAl, a bit-parallel algorithm for general, integer-scoring global alignment.In timed tests, we show that BitPAl runs 7-25 times faster than a standard iterative algorithm.

View Article: PubMed Central - PubMed

Affiliation: Laboratory for Biocomputing and Informatics, Graduate Program in Bioinformatics, and Department of Computer Science, Boston University, Boston, MA 02215, USA Laboratory for Biocomputing and Informatics, Graduate Program in Bioinformatics, and Department of Computer Science, Boston University, Boston, MA 02215, USA.

Show MeSH
Related in: MedlinePlus