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-F4: An example of the calculation of and values. values come from the previous row. The match locations and the leftmost value are known. The value for a particular column is found using the table in Figure 3. The input is the value in the same column and the value in the column to the left, except, when there is a match, the value in the column to the left is treated as a and, starting with Step 3, if the value in the column to the left is not assigned, it is treated as mid. †is a modification of in which all Match positions have been changed to and all values less than mid have been changed to mid. The value for a particular column is found using the transpose of the table in Figure 3. The input is the †in the same column and the value in the column to the left Mentions: the match positions in the current row.

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-F4: An example of the calculation of and values. values come from the previous row. The match locations and the leftmost value are known. The value for a particular column is found using the table in Figure 3. The input is the value in the same column and the value in the column to the left, except, when there is a match, the value in the column to the left is treated as a and, starting with Step 3, if the value in the column to the left is not assigned, it is treated as mid. †is a modification of in which all Match positions have been changed to and all values less than mid have been changed to mid. The value for a particular column is found using the transpose of the table in Figure 3. The input is the †in the same column and the value in the column to the left
Mentions: the match positions in the current row.

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