Multiple sequence alignment for short sequences
Multiple sequence alignment (MSA) has been one of the most important problems in bioinformatics for more decades and it is still heavily examined by many mathematicians and biologists. However, mostly because of the practical motivation of this problem, the research on this topic is focused on aligning long sequences. It is understandable, since the sequences that need to be aligned (usually DNA or protein sequences) are generally quite long (e. g., at least 30-40 characters). Nevertheless, it is a challenging question that exactly where MSA starts to become a real hard problem (since it is known that MSA is NP-complete [2]), and the key to answer this question is to examine short sequences. If the optimal alignment for short sequences could be determined in polynomial time, then these results may help to develop faster or more accurate heuristic algorithms for aligning long sequences. In this work, it is shown that for length-1 sequences using arbitrary metric, as well as for length-2 sequences using unit metric, the optimum of the MSA problem can be achieved by the trivial alignment.
Code (0)
등록된 구현이 없습니다.
Tasks
Multiple Sequence AlignmentSimilar Papers 제목 키워드 기반
Locality Sensitive Hashing-based Sequence Alignment Using Deep Bidirectional LSTM Models
Bidirectional Long Short-Term Memory (LSTM) is a special kind of Recurrent Neural Network (RNN) architecture which is designed to model sequences and their long-range dependencies more precisely than RNNs. This paper pro…
DLPAlign: A Deep Learning based Progressive Alignment Method for Multiple Protein Sequences
This paper proposed a novel and straightforward approach to improve the accuracy of progressive multiple protein sequence alignment method. We trained a decision-making model based on the convolutional neural networks an…
Decision MakingMultiple Sequence AlignmentProtein Secondary Structure PredictionA Novel Method for Comparative Analysis of DNA Sequences by Ramanujan-Fourier Transform
Alignment-free sequence analysis approaches provide important alternatives over multiple sequence alignment (MSA) in biological sequence analysis because alignment-free approaches have low computation complexity and are …
ClusteringMultiple Sequence AlignmentA Light-Weight Contrastive Approach for Aligning Human Pose Sequences
We present a simple unsupervised method for learning an encoder mapping short 3D pose sequences into embedding vectors suitable for sequence-to-sequence alignment by dynamic time warping. Training samples consist of temp…
Dynamic Time WarpingbenchNGS : An approach to benchmark short reads alignment tools
In the last decade a number of algorithms and associated software have been developed to align next generation sequencing (NGS) reads with relevant reference genomes. The accuracy of these programs may vary significantly…