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 MajorAlgorithms*Sequence Alignment/methods*MinorHigh-Throughput Nucleotide SequencingSoftware Related in: MedlinePlus © Copyright Policy - creative-commons Related In: Results  -  Collection License getmorefigures.php?uid=PMC4221118&req=5 .flowplayer { width: px; height: px; } btu507-F1: Zones in the Function Table for ΔV. Zone A: all values are in ; Zone B: all values are in ; Zone C: all values are in and values depend only on ΔH; Zone D: all values are G; Last row: values also apply when there is a match;. First column: identity column for values in 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)

Related In: Results  -  Collection

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

btu507-F1: Zones in the Function Table for ΔV. Zone A: all values are in ; Zone B: all values are in ; Zone C: all values are in and values depend only on ΔH; Zone D: all values are G; Last row: values also apply when there is a match;. First column: identity column for values in
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