Multiple Sequence Alignment of the M Protein in SARS-Associated and Other Known Coronaviruses

In this paper, we report a multiple sequence alignment result on the basis of 10 amino acid sequences of the M protein, which come from different coronaviruses (4 SARS associated and 6 others known). The alignment model was based on the profile HMM (Hidden Markov Model), and the model training was implemented through the SAHMM (Self Adapting Hidden Markov Model) software developed by the authors.

Brief Introduction to Self-Adapting Hidden Markov Model Program for Multiple Sequences Alignment

In this letter, we briefly describe a program of self adapting hidden Markov model (SA HMM) and its application in multiple sequences alignment. Program consists of two stage optimisation algorithm.

Exploring the Effects of Gap-Penalties in Sequence-Alignment Approach to Polymorphic Virus Detection

Antiviral software systems (AVSs) have problems in identifying polymorphic variants of viruses without explicit signatures for such variants. Alignment-based techniques from bioinformatics may provide a novel way to generate signatures from consensuses found in polymorphic variant code. We demonstrate how multiple sequence alignment supplemented with gap penalties leads to viral code signatures that generalize successfully to previously known polymorphic variants of JS. Cassandra virus and previously unknown polymorphic variants of W32.CTX/W32.Cholera and W32.Kitti viruses. The implications are that future smart AVSs may be able to generate effective signatures automatically from actual viral code by varying gap penalties to cover for both known and unknown polymorphic variants.

Artificial Fish Swarm for Multi Protein Sequences Alignment in Bioinformatics

The alignment operation between many protein sequences or DNAsequences related to the scientific bioinformatics application is very complex.There is a trade-off in the objectives in the existing techniques of MultipleSequence Alignment (MSA). The techniques that concern with speed ignoreaccuracy, whereas techniques that concern with accuracy ignore speed. Theterm alignment means to get the similarity in different sequences with highaccuracy. The more growing number of sequences leads to a very complexand complicated problem. Because of the emergence;rapid development;anddependence on gene sequencing, sequence alignment has become importantin every biological relationship analysis process. Calculating the numberof similar amino acids is the primary method for proving that there is arelationship between two sequences. The time is a main issue in any alignmenttechnique. In this paper, a more effective MSA method for handling themassive multiple protein sequences alignment maintaining the highest accuracy with less time consumption is proposed. The proposed method dependson Artificial Fish Swarm (AFS) algorithm that can break down the mostchallenges of MSA problems. The AFS is exploited to obtain high accuracyin adequate time. ASF has been increasing popularly in various applicationssuch as artificial intelligence, computer vision, machine learning, and dataintensive application. It basically mimics the behavior of fish trying to getthe food in nature. The proposed mechanisms of AFS that is like preying,swarming, following, moving, and leaping help in increasing the accuracy andconcerning the speed by decreasing execution time. The sense organs that aidthe artificial fishes to collect information and vision from the environmenthelp in concerning the accuracy. These features of the proposed AFS make thealignment operation more efficient and are suitable especially for large-scaledata. The implementation and experimental results put the proposed AFS as afirst choice in the queue of alignment compared to the well-known algorithmsin multiple sequence alignment.

多重序列比对Alignment的信息度量准则

多重序列的比对(Alignment)的核心问题是对多重DNA(或RNA、蛋白质)序列,寻找它们的相似部分或稳定区域,但如何定义多重序列的相似度(或罚分函数)则是解决多重序列比对的前提。首先对多重序列相似度的合理性进行了讨论,给出了一组合理的相似度所必需具备的条件;再利用Shannon熵的特点,给出一个满足这些合理性条件的多重序列比对的优化准则。

Genetic Diversity of Chinese Soybean mosaic virus Strains and Their Relationships with Other Plant Potyviruses Based on P3 Gene Sequences

Soybean mosaic virus （SMV）, a member of the genus Potyvirus, is a major pathogen of soybean plants in China, and 16 SMV strains have been identified nationwide based on a former detailed SMV classification system. As the P3 gene is thought to be involved in viral replication, systemic infection, pathogenicity, and overcoming resistance, knowledge of the P3 gene sequences of SMV and other potyviruses would be useful in efforts to know the genetic relationships among them and control the disease. P3 gene sequences were obtained from representative isolates of the above-mentioned 16 SMV strains and were compared with other SMV strains and 16 Potyvirus species from the National Center for Biotechnology GenBank database. The P3 genes from the 16 SMV isolates are composed of 1041 nucleotides, encoding 347 amino acids, and share 90.7-100% nucleotide （NT） sequence identities and 95.1-100% amino acid （AA） sequence identities. The P3 coding regions of the 16 SMV isolates share high identities （92.4-98.9% NT and 96.0-100% AA） with the reported Korean isolates, followed by the USA isolates （88.5-97.9% NT and 91.4-98.6% AA）, and share low identities （80.5-85.2% NT and 82.1-84.7% AA） with the reported HZ 1 and P isolates from Pinellia ternata. The sequence identities of the P3 genes between SMV and the 16 potyviruses varied from 44.4 to 81.9% in the NT sequences and from 21.4 to 85.3% in the AA sequences, respectively. Among them, SMV was closely related to Watermelon mosaic virus （WMV）, with 76.0-81.9% NT and 77.5-85.3% AA identities. In addition, the SMV isolates and potyvirus species were clustered into six distinct groups. All the SMV strains isolated from soybean were clustered in Group I, and the remaining species were clustered in other groups. A multiple sequence alignment analysis of the C-terminal regions indicated that the P3 genes within a species were highly conserved, whereas those among species were relatively variable.

FASMA:A Service to Format and Analyze Sequences in Multiple Alignments

Multiple sequence alignments are successfully applied in many studies for understanding the structural and functional relations among single nucleic acids and protein sequences as well as whole families. Because of the rapid growth of sequence databases, multiple sequence alignments can often be very large and difficult to visualize and analyze. We offer a new service aimed to visualize and analyze the multiple alignments obtained with different external algorithms, with new features useful for the comparison of the aligned sequences as well as for the creation of a final image of the alignment. The service is named FASMA and is available at http： / /bioinformatica.isa.cnr.it /FASMA /.

On the Edge of Web-Based Multiple Sequence Alignment Services

There are many web-based multiple sequence alignment services accessible around the world. However, many researchers working on biological sequence analysis still struggle with inefficient, unfriendly user interface, and limited capability multiple sequence alignment software. In this study, we provide a comprehensive survey of regional and continental facilities that provide web-based alignment services. We also analyze and identify much needed services that are not available through these existing service providers. We then implement a web-based model to address these needs. From that perspective, our web-based multiple sequence alignment server, SeqAna, provides a unique set of services that none of these studied facilities have. For example, SeqAna provides a multiple sequence alignment scoring and ranking service. This service, the only of its kind, allows SeqAna＇s users to perform multiple sequence alignment with several alignment tools and rank the results of these alignments in the order of quality. With this service, SeqAna＇s users will be able to identify which alignment tools are more appropriate for their specific set of sequences. In addition, SeqAna＇s users can customize a small alignment sample as a reference for SeqAna to automatically identify the best tool to align their large set of sequences.

VCSRA:A fast and accurate multiple sequence alignment algorithm with a high degree of parallelism

Multiple sequence alignment （MSA） is the alignment among more than two molecular biological sequences, which is a fundamental method to analyze evolutionary events such as mutations, insertions, deletions, and re-arrangements. In theory, a dynamic programming algorithm can be employed to produce the optimal MSA. However, this leads to an explosive increase in computing time and memory consumption as the number of sequences increases （Taylor, 1990）. So far, MSA is still regarded as one of the most challenging problems in bioinformatics and computational biology （Chatzou et al., 2016）.

Fast vectorized distance matrix computation for multiple sequence alignment on multi-cores

Although high quality multiple sequence alignment is an essential task in bioinforma- tics, it becomes a big dilemma nowadays due to the gigantic explosion in the amount of molecular data. The most consuming time and space phase is the distance matrix computation. This paper addresses this issue by proposing a vectorized parallel method that accomplishes the huge number of similarity comparisons faster in less space. Per- formance tests on real biological datasets using core-iT show superior results in terms of time and space.

ORPA:a fast and efficient phylogenetic analysis method for constructing genome-wide alignments of organelle genomes

Creating a multi-gene alignment matrix for phylogenetic analysis using organelle genomes involves aligning single-gene datasets manually,a process that can be time-consuming and prone to errors.The HomBlocks pipeline has been created to eliminate the inaccuracies arising from manual operations.The processing of a large number of sequences,however,remains a time-consuming task.To conquer this challenge,we develop a speedy and efficient method called Organelle Genomes for Phylogenetic Analysis(ORPA).ORPA can quickly generate multiple sequence alignments for whole-genome comparisons by parsing the result files of NCBI BLAST,completing the task just in 1 min.With increasing data volume,the efficiency of ORPA is even more pronounced,over 300 times faster than HomBlocks in aligning 60 high-plant chloroplast genomes.The phylogenetic tree outputs from ORPA are equivalent to HomBlocks,indicating its outstanding efficiency.Due to its speed and accuracy,ORPA can identify species-level evolutionary conflicts,providing valuable insights into evolutionary cognition.

求解MSA问题的新型单亲遗传算法

多序列联配(MSA)在生物信息学研究中占有重要地位,MSA问题是一个典型的NP问题,遗传算法是求解NP完全问题的一种理想方法。文章针对MSA问题,提出了一种新型单亲遗传算法(PGA),不使用交叉算子,只使用变异和选择算子。并根据群体的多样性自适应调节变异概率,有效消除了算法中的欺骗性条件,使用灾变算子来确保算法的搜索能力。整个算法模拟了自然界进化的周期性,较好地解决了群体的多样性和收敛深度的矛盾。算法的分析和测试表明,该算法是有效的。

求解MSA问题的新型遗传算法

为了克服传统遗传算法求解MSA问题速度慢的缺点,提出了一种新型自适应遗传算法,不使用交叉算子,只使用变异和选择算子.提出了在算法初始化时引入种子的策略,用星比对算法生成一个种子,保证了解的质量,使用灾变算子来确保算法的搜索能力.该算法模拟了自然界进化的周期性,较好地解决了群体多样性和收敛深度的矛盾.

一种求解MSA问题的自适应遗传算法

多序列比对(MSA)在生物信息学研究中占有重要地位,MSA问题是一个典型的NP问题,遗传算法是求解NP完全问题的一种有效方法。文章针对MSA问题,提出了一种新型自适应遗传算法,根据群体的多样性自适应调节变异概率,有效消除了算法中的欺骗性条件,使用突变算子来确保算法的搜索能力。整个算法模拟了自然界进化的周期性,较好的解决了群体的多样性和收敛深度的矛盾。算法的分析和测试表明,该算法是有效的。

一种面向生物基因多序列比对算法的任务调度方法

针对现阶段生物基因多序列比对算法在面对大规模数据时存在比对效率慢的问题,提出一种面向生物基因多序列比对算法的任务调度方法,以提高生物基因多序列比对的效率。通过Trie树方法对生物基因多序列数据展开分割处理,从而提高后续基因多序列比对过程中数据查找和匹配的效率;构建基因多序列BWT索引,利用BWT索引方法完成生物基因多序列比对;以多序列比对方法为基础,采用CPU与GPU异构并行系统完成多序列比对的任务调度。实验结果表明,所提的面向生物基因多序列比对算法的任务调度方法效率更高、性能更好,且更适合于实际应用。

BitmapAligner:Bit-Parallelism String Matching with MapReduce and Hadoop

Advancements in next-generation sequencer(NGS)platforms have improved NGS sequence data production and reduced the cost involved,which has resulted in the production of a large amount of genome data.The downstream analysis of multiple associated sequences has become a bottleneck for the growing genomic data due to storage and space utilization issues in the domain of bioinformatics.The traditional string-matching algorithms are efficient for small sized data sequences and cannot process large amounts of data for downstream analysis.This study proposes a novel bit-parallelism algorithm called BitmapAligner to overcome the issues faced due to a large number of sequences and to improve the speed and quality of multiple sequence alignment(MSA).The input files(sequences)tested over BitmapAligner can be easily managed and organized using the Hadoop distributed file system.The proposed aligner converts the test file(the whole genome sequence)into binaries of an equal length of the sequence,line by line,before the sequence alignment processing.The Hadoop distributed file system splits the larger files into blocks,based on a defined block size,which is 128 MB by default.BitmapAligner can accurately process the sequence alignment using the bitmask approach on large-scale sequences after sorting the data.The experimental results indicate that BitmapAligner operates in real time,with a large number of sequences.Moreover,BitmapAligner achieves the exact start and end positions of the pattern sequence to test the MSA application in the whole genome query sequence.The MSA’s accuracy is verified by the bitmask indexing property of the bit-parallelism extended shifts(BXS)algorithm.The dynamic and exact approach of the BXS algorithm is implemented through the MapReduce function of Apache Hadoop.Conversely,the traditional seeds-and-extend approach faces the risk of errors while identifying the pattern sequences’positions.Moreover,the proposed model resolves the largescale data challenges that are covered through MapReduce in the Hadoop framework.Hive,Yarn,HBase,Cassandra,and many other pertinent flavors are to be used in the future for data structuring and annotations on the top layer of Hadoop since Hadoop is primarily used for data organization and handles text documents.

基于协同变异与莱维飞行策略的教与学优化算法及其应用

针对教与学优化(TLBO)算法在处理优化问题时存在搜索不均衡、易陷入局部最优、综合求解性能弱等缺陷,提出一种基于均衡优化与莱维飞行策略的改进教与学优化算法ELMTLBO。首先设计精英均衡引导策略,通过种群中多个精英个体的均衡引导提高算法的全局寻优能力;其次在TLBO算法的学习者阶段后,利用自适应权重策略对莱维飞行产生的步长进行自适应缩量,以提高种群局部寻优能力,增强个体对复杂环境的自适应性;最后设计了变异算子池逃逸策略,通过多个变异算子的协同引导,提升算法的种群多样性。为验证算法改进的有效性,将EMLTLBO算法与侏儒猫鼬优化算法(DMOA)等先进的智能优化算法以及平衡教与学优化(BTLBO)算法、标准TLBO等同类型算法在15个国际测试函数上进行综合收敛性能比较。统计实验结果表明,与先进的智能优化算法和TLBO算法变体相比,ELMTLBO算法能够有效平衡其搜索能力,不但有效求解单峰和多峰问题,而且在复杂多峰问题上仍有显著的寻优能力。在不同策略的共同作用下,ELMTLBO算法的综合优化性能突出,全局收敛性能较为稳定。此外,ELMTLBO算法成功应用于基于隐马尔可夫模型(HMM)的多序列比对(MSA)问题中,优化后得到的高质量对齐序列可用于疾病诊断、基因溯源等,可为生物信息学提供算法支撑。

水平聚类分簇和垂直分组的大规模长序列多比对

为解决现有算法在大规模长序列数据集上耗时过长的问题,提出一种融合水平聚类分簇和垂直分组的多序列比对方法.采用mBed方法和简并字母表方法将序列集编码为数值向量集,利用二分k-means算法聚类数值向量集并将序列集划分成多个水平簇;提出最长兼容链构建算法和簇内序列垂直分割方法,进而设计簇内序列垂直分组方法将每个水平簇划分为多个垂直分组,分别比对各垂直分组,以获得各个水平簇内序列的比对结果;设计针对水平簇集的簇间序列垂直分组方法和带有Gap类型推断的动态规划渐进比对方法,将长序列集垂直划分为多个簇间分组并分别进行对准,以实现大规模长序列的比对.实验结果表明,与同类算法相比,本文方法在维持较高比对精度的同时,显著地减少了比对的时间开销.

2株猪繁殖与呼吸综合征病毒海南株的ORF5基因分析

【目的】鉴定我国海南省新发现的2株猪繁殖与呼吸综合征病毒株HNHK1-2021和HNLG1-2021的进化关系。【方法】采用PCR方法对ORF5基因进行扩增和序列测定,利用MegAlign软件进行多重序列比对,利用MEGA X软件邻接法构建进化树。【结果】PRRSV HNHK1-2021和HNLG1-2021毒株核苷酸相似性为82.9%,推导氨基酸相似性为82.6%。HNHK1-2021毒株和NADC30类PRRSV、QYYZ类PRRSV、VR-2332类PRRSV以及JXA1类PRRSV序列比对,80.8%~82.8%、90.2%~92.0%、82.1%~83.4%、81.9%~84.4%,推导氨基酸相似性分别为82.1%~84.6%、91.5%~94.5%、80.1%~83.1%、82.6%~84.6%;HNLG1-2021毒株和NADC30类PRRSV、QYYZ类PRRSV、VR2332类PRRSV以及JXA1类PRRSV序列比对,核苷酸相似性分别为83.7%~84.6%、81.8%~83.6%、97.7%~99.5%、85.6%~90.4%,推导氨基酸相似性为83.6%~85.1%、81.1%~82.6%、96.0%~98.5%,86.1%~90.5%。【结论】2株病毒株均属于北美型PRRSV,HNHK1-2021毒株属于QYYZ类PRRSV(谱系3)。HNLG1-2021毒株属于VR-2332类PRRSV(谱系5)。

一个新的强化学习多序列对比工具CDRL

多序列比对(multiple sequence alignment, MSA)在生物信息学中是一项重要的研究领域,常被用于描述物种之间的进化关系、药物设计和药物开发.MSA是一个NP完全问题,因计算过于复杂,无法获得最优解.强化学习方法在MSA中表现出了优异的性能,但其计算复杂度与空间复杂度都很高,因此无法应用于大规模数据集.提出一种新的强化学习模型CDRL(contextual deep reinforcement learning)来解决多序列比对问题,该模型采用上下文关系,将网络输入维度从O(n2)降为O(n),其中n是输入的序列数量.该模型建立的网络收敛速度快于当前其他模型.实验结果表明,CDRL的性能优于业内其他强化学习MSA.相较于其他方法目前只能运行在12条序列数据上,CDRL成功地在100条序列上取得较快速度和较好性能.这提高了强化学习MSA应用在较大规模数据集上的可能性.