Bit-Parallel Algorithm for the Block Variant of the Merged Longest Common Subsequence Problem

descriptionPublicationkeyboard_double_arrow_right Part of book or chapter of book , Conference object , Other literature type 01 Jan 2014 English Publisher:Springer International Publishing

Authors: Agnieszka Danek; Sebastian Deorowicz;

doi: 10.1007/978-3-319-02309-0_18

Bit-Parallel Algorithm for the Block Variant of the Merged Longest Common Subsequence Problem

- Summary
- Metrics

Abstract

The problem of comparison of genomic sequences is of great importance. There are various measures of similarity of sequences. One of the most popular is the length of the longest common subsequence (LCS). We propose the first bit-parallel algorithm for the variant of the LCS problem, block merged LCS, which was recently formulated in the studies on the whole genome duplication hypothesis. Practical experiments show that our proposal is from 10 to over 100 times faster than existing algorithms.

Related Organizations

Silesian University of Technology
Poland

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	1
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average