Two Efficient Techniques to Find Approximate Overlaps between Sequences
Autor: | Maan Haj Rachid |
---|---|
Jazyk: | angličtina |
Rok vydání: | 2017 |
Předmět: |
0301 basic medicine
Article Subject Computer science lcsh:Medicine General Biochemistry Genetics and Molecular Biology Machine Learning 03 medical and health sciences Software Redundancy (information theory) Trie Humans Models Statistical General Immunology and Microbiology Spacetime business.industry Genome Human Pigeonhole principle lcsh:R Computational Biology High-Throughput Nucleotide Sequencing Hamming distance General Medicine Sequence Analysis DNA 030104 developmental biology Ordered pair Approximate matching Programming Languages business Algorithm Algorithms Research Article |
Zdroj: | BioMed Research International BioMed Research International, Vol 2017 (2017) |
Popis: | The next-generation sequencing (NGS) technology outputs a huge number of sequences (reads) that require further processing. After applying prefiltering techniques in order to eliminate redundancy and to correct erroneous reads, an overlap-based assembler typically finds the longest exact suffix-prefix match between each ordered pair of the input reads. However, another trend has been evolving for the purpose of solving an approximate version of the overlap problem. The main benefit of this direction is the ability to skip time-consuming error-detecting techniques which are applied in the prefiltering stage. In this work, we present and compare two techniques to solve the approximate overlap problem. The first adapts a compact prefix tree to efficiently solve the approximate all-pairs suffix-prefix problem, while the other utilizes a well-known principle, namely, the pigeonhole principle, to identify a potential overlap match in order to ultimately solve the same problem. Our results show that our solution using the pigeonhole principle has better space and time consumption over an FM-based solution, while our solution based on prefix tree has the best space consumption between all three solutions. The number of mismatches (hamming distance) is used to define the approximate matching between strings in our work. |
Databáze: | OpenAIRE |
Externí odkaz: |