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 mod...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.展开更多
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-ar...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).展开更多
The task of clustering Web sessions is to group Web sessions based on similarity and consists of maximizing the intra-group similarity while minimizing the inter-group similarity. The first and foremost question neede...The task of clustering Web sessions is to group Web sessions based on similarity and consists of maximizing the intra-group similarity while minimizing the inter-group similarity. The first and foremost question needed to be considered in clustering Web sessions is how to measure the similarity between Web sessions. However, there are many shortcomings in traditional measurements. This paper introduces a new method for measuring similarities between Web pages that takes into account not only the URL but also the viewing time of the visited Web page. Then we give a new method to measure the similarity of Web sessions using sequence alignment and the similarity of Web page access in detail Experiments have proved that our method is valid and efficient.展开更多
Eukaryotic genomes contain a significant fraction of repeats, which have very important biomedical function. Thus, aligning repeats from short sequences back to reference genome is the key step for further genome anal...Eukaryotic genomes contain a significant fraction of repeats, which have very important biomedical function. Thus, aligning repeats from short sequences back to reference genome is the key step for further genome analysis. Unfortunately, the current aligning algorithms performed poorly in distinguishing repeats and nonrepeats. To this end, we proposed a new algorithm, named HashRepAligner, to address this problem. Finally, the cross comparison with other algorithms was performed, and the results indicated that HashRepAligner outperformed other aligners in terms of the detecting repeats.展开更多
With the rapid development of Next-Generation Sequencing(NGS)technology,genome sequencing services for clinical fields are now bringing new challenges to existing solutions.The increasing demand for alignment data pro...With the rapid development of Next-Generation Sequencing(NGS)technology,genome sequencing services for clinical fields are now bringing new challenges to existing solutions.The increasing demand for alignment data processing motivates the development of more efficient algorithms for computational genomics.The Pair-Hidden Markov Model(Pair-HMM)is one of the most popular models used to process sequence alignment.Its related Forward Algorithm(FA)is usually the key performance bottleneck of the entire variant calling workflow.While multiple previous works have been conducted in efforts to accelerate the algorithm with various levels of parallelization,it still lacks of fully utilizing the resources of heterogeneous devices,such as high-bandwidth memory and massive SIMD cores in advanced GPU.In this paper,we design a GPU-based Pari-HMM sequence alignment algorithm and conduct its implementation with holistic co-design optimizations,including efficient computational parallelization,parameter initialization,memory accessing layout,and etc.When using Nvidia Telsa V100 GPU,Our work has shown speedups of 1151x compared to the Java baseline on Intel single-core CPU and 1.47x to the previous state-of-art GPU work.展开更多
MegaBlast is one of the most important programs in NCBI BLAST (Basic Local Alignment Search Tool) toolkits, tIowever, MegaBlast is computation and I/O intensive. It consumes a great deal of memory which is proportio...MegaBlast is one of the most important programs in NCBI BLAST (Basic Local Alignment Search Tool) toolkits, tIowever, MegaBlast is computation and I/O intensive. It consumes a great deal of memory which is proportional to the size of the query sequences set and subject (database) sequences set of product. This paper proposes a new strategy for optimizing MegaBlast. The new strategy exchanges the query and subject sequences sets, and builds a hash table based on new subject sequences. It overlaps I/O with computation, shortens the overall time and reduces the cost of memory, since the memory here is only proportional to the size of subject sequences set. The optimized algorithm is suitable to be parallelized in cluster systems. The parallel algorithm uses query segmentation method. As our experiments shown, the parallel program which is implemented with MPI has fine scalability.展开更多
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 Multiple...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.展开更多
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 ...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.展开更多
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, ...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.展开更多
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.
Due to current technology enhancement,molecular databases have exponentially grown requesting faster efficient methods that can handle these amounts of huge data.There-fore,Multi-processing CPUs technology can be used...Due to current technology enhancement,molecular databases have exponentially grown requesting faster efficient methods that can handle these amounts of huge data.There-fore,Multi-processing CPUs technology can be used including physical and logical processors(Hyper Threading)to significantly increase the performance of computations.Accordingly,sequence comparison and pairwise alignment were both found contributing significantly in calculating the resemblance between sequences for constructing optimal alignments.This research used the Hash Table-NGram-Hirschberg(HT-NGH)algo-rithm to represent this pairwise alignment utilizing hashing capabilities.The authors propose using parallel shared memory architecture via Hyper Threading to improve the performance of molecular dataset protein pairwise alignment.The proposed parallel hyper threading method targeted the transformation of the HT-NGH on the datasets decomposition for sequence level efficient utilization within the processing units,that is,reducing idle processing unit situations.The authors combined hyper threading within the multicore architecture processing on shared memory utilization remarking perfor-mance of 24.8%average speed up to 34.4%as the highest boosting rate.The benefit of this work improvement is shown preserving acceptable accuracy,that is,reaching 2.08,2.88,and 3.87 boost-up as well as the efficiency of 1.04,0.96,and 0.97,using 2,3,and 4 cores,respectively,as attractive remarkable results.展开更多
Root rot is a prevalent soil-borne fungal disease in citrus.Citron C-05(Citrus medica)stands out as a germplasm within Citrus spp.due to its complete resistance to citrus canker and favorable characteristics such as s...Root rot is a prevalent soil-borne fungal disease in citrus.Citron C-05(Citrus medica)stands out as a germplasm within Citrus spp.due to its complete resistance to citrus canker and favorable characteristics such as single embryo and easy rooting.However,Citron C-05 was found to be highly susceptible to root rot during cultivation,with the specific pathogens previously unknown.In this study,four candidate fungal species were isolated from Citron C-05 roots.Sequence analysis of ITS,EF-1a,RPB1,and RPB2 identified two Fusarium solani strains,Rr-2 and Rr-4,as the candidates causing root rot in Citron C-05.Resistance tests showed these two pathogens increased root damage rate from 10.30%to 35.69%in Citron C-05,sour orange(Citrus aurantium),sweet orange(Citrus sinensis)and pummelo(Citrus grandis).F.solani exhibited the weak pathogenicity towards trifoliate orange(Poncirus trifoliata).DAB staining revealed none of reddish-brown precipitation in the four susceptible citrus germplasm after infection with F.solani,while trifoliate orange exhibited significant H2O2 accumulation.Trypan blue staining indicated increased cell death in the four susceptible citrus germplasm following infection with these two pathogens but not in trifoliate orange.These findings provide a comprehensive understanding of citrus root rot and support future research on the mechanisms of root rot resistance in citrus.展开更多
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 ...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.展开更多
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. A...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.展开更多
Existing studies have challenged the current definition of named bacterial species,especially in the case of highly recombinogenic bacteria.This has led to considering the use of computational procedures to examine po...Existing studies have challenged the current definition of named bacterial species,especially in the case of highly recombinogenic bacteria.This has led to considering the use of computational procedures to examine potential bacterial clusters that are not identified by species naming.This paper describes the use of sequence data obtained from MLST databases as input for a k-means algorithm extended to deal with housekeeping gene sequences as a metric of similarity for the clustering process.An implementation of the k-means algorithm has been developed based on an existing source code implementation,and it has been evaluated against MLST data.Results point out to potential bacterial clusters that are close to more than one different named species and thus may become candidates for alternative classifications accounting for genotypic information.The use of hierarchical clustering with sequence comparison as similarity metric has the potential to find clusters different from named species by using a more informed cluster formation strategy than a conventional nominal variant of the algorithm.展开更多
A computer-aided method to design a hybrid layout--tree-shape planar flowlines is presented. In newtype fiowshop layout, the common machines shared by several flowlines could be located together in functional sections...A computer-aided method to design a hybrid layout--tree-shape planar flowlines is presented. In newtype fiowshop layout, the common machines shared by several flowlines could be located together in functional sections. The approach combines traditional cell formation techniques with sequence alignment algorithms. Firstly, a sequence analysis based cell formation procedure is adopted; then the operation sequences for parts are aligned to maximize machines adjacency in hyperedge representations; finally a tree-shape planar flowline will be obtained for each part family. With the help of a sample of operation sequences obtained from industry, this algorithm is illustrated.展开更多
In 2009, an emerging citrus viral disease caused by Citrus chlorotic dwarf-associated virus(CCDaV) was discovered in Yunnan Province of China. However, the occurrence and spread of CCDaV in other citrus-growing provin...In 2009, an emerging citrus viral disease caused by Citrus chlorotic dwarf-associated virus(CCDaV) was discovered in Yunnan Province of China. However, the occurrence and spread of CCDaV in other citrus-growing provinces in China is unknown to date. To better understand the distribution and molecular diversity of CCDaV in China, a total of 1 772 citrus samples were collected from 11 major citrus-growing provinces and were tested for CCDaV by PCR. Among these, 134 citrus samples from Guangxi, Yunnan and Guangdong were tested positive for CCDaV, demonstrating that the occurrence and spread of CCDaV are increasing in China. The complete genome sequences of 17 CCDaV isolates from different provinces and hosts were sequenced. Comparisons of the whole-genome sequences of the 17 CCDaV isolates as well as the 15 isolates available in GenBank revealed that the sequence identity was about 99–100%, showing that the CCDaV isolates were highly conserved. Phylogenetic studies showed that the 32 CCDaV isolates belonged to four different groups based on geographical origins and host species, and that CCDaV isolates from China and Turkey were clustered into different groups. The results provide important information for clarifying the distribution and genetic diversity of CCDaV in China.展开更多
[Objective] The aim was to identify genetic variation in Citrus sinensis (sweet orange) germplasm from Hunan Province according to the Start Codon Targeted (SCoT) Polymorphism. [Method] The reaction system for SCo...[Objective] The aim was to identify genetic variation in Citrus sinensis (sweet orange) germplasm from Hunan Province according to the Start Codon Targeted (SCoT) Polymorphism. [Method] The reaction system for SCoT amplification from sweet orange was first optimized, and then the SCoT fragments were amplified from 24 sweet orange cultivars collected in Hunan Province and sequenced for genetic variation analysis. [Result] The optimum reaction system for SCoT markers amplification was 2.0 μl containing 80 ng of template DNA, 0.3 mmol/L dNTPs, 0.2 μmol/L primer, 1.6 mmol/L Mg2+, 1.6 U of Taq DNA polymerase and 10×PCR buffer. By using this reaction system, the PCR products from the sweet orange cultivars produced clear and reproducible bands at 100-2 000 bp through electrophoresis. The SCoT fragments of the 24 sweet orange cultivars were 1 090-1 091 bp, with the homology of 99.84% and nucleotide deletion and substitution. After being sequenced, the SCoT polymorphisms could distinguish 12 sweet orange cultivars. In addition, the BLAST result showed that part of the SCoT fragments coding region shared high homology with ribosomal protein S3 N superfamily. [Conclusion] This study will provide a theoretical basis for breeding sweet orange cultivars.展开更多
Profile hidden Markov models (HMMs) based on classical HMMs have been widely applied for protein sequence identification. The formulation of the forward and backward variables in profile HMMs is made under statistic...Profile hidden Markov models (HMMs) based on classical HMMs have been widely applied for protein sequence identification. The formulation of the forward and backward variables in profile HMMs is made under statistical independence assumption of the probability theory. We propose a fuzzy profile HMM to overcome the limitations of that assumption and to achieve an improved alignment for protein sequences belonging to a given family. The proposed model fuzzifies the forward and backward variables by incorporating Sugeno fuzzy measures and Choquet integrals, thus further extends the generalized HMM. Based on the fuzzified forward and backward variables, we propose a fuzzy Baum-Welch parameter estimation algorithm for profiles. The strong correlations and the sequence preference involved in the protein structures make this fuzzy architecture based model as a suitable candidate for building profiles of a given family, since the fuzzy set can handle uncertainties better than classical methods.展开更多
A fundamental goal in cellular signaling is to understand allosteric communication, the process by which sig-nals originating at one site in a protein propagate reliably to affect distant functional sites. The general...A fundamental goal in cellular signaling is to understand allosteric communication, the process by which sig-nals originating at one site in a protein propagate reliably to affect distant functional sites. The general principles of protein structure that underlie this process remain unknown. Statistical coupling analysis (SCA) is a statistical technique that uses evolutionary data of a protein family to measure correlation between distant functional sites and suggests allosteric communication. In proteins, very distant and small interactions between collections of amino acids provide the communication which can be important for signaling process. In this paper, we present the SCA of protein alignment of the esterase family (pfam ID: PF00756) containing the sequence of antigen 85C secreted by Mycobacterium tuberculosis to identify a subset of interacting residues. Clustering analysis of the pairwise correlation highlighted seven important residue positions in the esterase family alignments. These resi-dues were then mapped on the crystal structure of antigen 85C (PDB ID: 1DQZ). The mapping revealed corre-lation between 3 distant residues (Asp38, Leu123 and Met125) and suggests allosteric communication between them. This information can be used for a new drug against this fatal disease.展开更多
摘要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.
基金supported by the National Key R&D Program of China (Nos. 2017YFB0202600, 2016YFC1302500, 2016YFB0200400 and 2017YFB0202104)the National Natural Science Foundation of China (Nos. 61772543, U1435222, 61625202, 61272056 and 61771331)Guangdong Provincial Department of Science and Technology (No. 2016B090918122)
摘要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).
基金Supported by the Foundation of Hubei Key Technology Research and Development(2005AA101C18)the Natural Science Founda-tion of South-Central University for Nationalities(YZY06009)
摘要The task of clustering Web sessions is to group Web sessions based on similarity and consists of maximizing the intra-group similarity while minimizing the inter-group similarity. The first and foremost question needed to be considered in clustering Web sessions is how to measure the similarity between Web sessions. However, there are many shortcomings in traditional measurements. This paper introduces a new method for measuring similarities between Web pages that takes into account not only the URL but also the viewing time of the visited Web page. Then we give a new method to measure the similarity of Web sessions using sequence alignment and the similarity of Web page access in detail Experiments have proved that our method is valid and efficient.
摘要Eukaryotic genomes contain a significant fraction of repeats, which have very important biomedical function. Thus, aligning repeats from short sequences back to reference genome is the key step for further genome analysis. Unfortunately, the current aligning algorithms performed poorly in distinguishing repeats and nonrepeats. To this end, we proposed a new algorithm, named HashRepAligner, to address this problem. Finally, the cross comparison with other algorithms was performed, and the results indicated that HashRepAligner outperformed other aligners in terms of the detecting repeats.
基金supported by National Key R&D Program of China under Grant 2022ZD0115304the National Natural Science Foundation of China under Grand No.62402534+1 种基金the GuangDong Basic and Applied Basic Research Foundation:2023A1515110117the Fundamental Research Funds for the Central Universities,Sun Yat-sen University:23xkjc016.
摘要With the rapid development of Next-Generation Sequencing(NGS)technology,genome sequencing services for clinical fields are now bringing new challenges to existing solutions.The increasing demand for alignment data processing motivates the development of more efficient algorithms for computational genomics.The Pair-Hidden Markov Model(Pair-HMM)is one of the most popular models used to process sequence alignment.Its related Forward Algorithm(FA)is usually the key performance bottleneck of the entire variant calling workflow.While multiple previous works have been conducted in efforts to accelerate the algorithm with various levels of parallelization,it still lacks of fully utilizing the resources of heterogeneous devices,such as high-bandwidth memory and massive SIMD cores in advanced GPU.In this paper,we design a GPU-based Pari-HMM sequence alignment algorithm and conduct its implementation with holistic co-design optimizations,including efficient computational parallelization,parameter initialization,memory accessing layout,and etc.When using Nvidia Telsa V100 GPU,Our work has shown speedups of 1151x compared to the Java baseline on Intel single-core CPU and 1.47x to the previous state-of-art GPU work.
基金Supported by the National Natural Science Foundation of China under Grant No. 60372040, Knowledge Innovative Project of Chinese Academy of Sciences under Grant No. KSCX2-SW-233 and 863 Grid Node of Hong Kong University under Grant No. 2002AA104530. Acknowledgements We would like to thank the anonymous reviewers for their suggestions on how to improve this paper, The experimental data sets are provided by Beijing Gcnomics Institute, Chinese Academy of Sciences.
摘要MegaBlast is one of the most important programs in NCBI BLAST (Basic Local Alignment Search Tool) toolkits, tIowever, MegaBlast is computation and I/O intensive. It consumes a great deal of memory which is proportional to the size of the query sequences set and subject (database) sequences set of product. This paper proposes a new strategy for optimizing MegaBlast. The new strategy exchanges the query and subject sequences sets, and builds a hash table based on new subject sequences. It overlaps I/O with computation, shortens the overall time and reduces the cost of memory, since the memory here is only proportional to the size of subject sequences set. The optimized algorithm is suitable to be parallelized in cluster systems. The parallel algorithm uses query segmentation method. As our experiments shown, the parallel program which is implemented with MPI has fine scalability.
基金The authors extend their appreciation to the Deanship of Scientific Research at Jouf University for funding this work through research Grant No(DSR2020–01–414).
摘要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.
摘要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.
摘要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.
摘要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.
基金Deanship of Scientific Research(DSR),King Abdulaziz University,Grant/Award Number:D-139-137-1441。
摘要Due to current technology enhancement,molecular databases have exponentially grown requesting faster efficient methods that can handle these amounts of huge data.There-fore,Multi-processing CPUs technology can be used including physical and logical processors(Hyper Threading)to significantly increase the performance of computations.Accordingly,sequence comparison and pairwise alignment were both found contributing significantly in calculating the resemblance between sequences for constructing optimal alignments.This research used the Hash Table-NGram-Hirschberg(HT-NGH)algo-rithm to represent this pairwise alignment utilizing hashing capabilities.The authors propose using parallel shared memory architecture via Hyper Threading to improve the performance of molecular dataset protein pairwise alignment.The proposed parallel hyper threading method targeted the transformation of the HT-NGH on the datasets decomposition for sequence level efficient utilization within the processing units,that is,reducing idle processing unit situations.The authors combined hyper threading within the multicore architecture processing on shared memory utilization remarking perfor-mance of 24.8%average speed up to 34.4%as the highest boosting rate.The benefit of this work improvement is shown preserving acceptable accuracy,that is,reaching 2.08,2.88,and 3.87 boost-up as well as the efficiency of 1.04,0.96,and 0.97,using 2,3,and 4 cores,respectively,as attractive remarkable results.
基金supported by Joint Funds of the National Natural Science Foundation of China(Grant No.U21A20228).
摘要Root rot is a prevalent soil-borne fungal disease in citrus.Citron C-05(Citrus medica)stands out as a germplasm within Citrus spp.due to its complete resistance to citrus canker and favorable characteristics such as single embryo and easy rooting.However,Citron C-05 was found to be highly susceptible to root rot during cultivation,with the specific pathogens previously unknown.In this study,four candidate fungal species were isolated from Citron C-05 roots.Sequence analysis of ITS,EF-1a,RPB1,and RPB2 identified two Fusarium solani strains,Rr-2 and Rr-4,as the candidates causing root rot in Citron C-05.Resistance tests showed these two pathogens increased root damage rate from 10.30%to 35.69%in Citron C-05,sour orange(Citrus aurantium),sweet orange(Citrus sinensis)and pummelo(Citrus grandis).F.solani exhibited the weak pathogenicity towards trifoliate orange(Poncirus trifoliata).DAB staining revealed none of reddish-brown precipitation in the four susceptible citrus germplasm after infection with F.solani,while trifoliate orange exhibited significant H2O2 accumulation.Trypan blue staining indicated increased cell death in the four susceptible citrus germplasm following infection with these two pathogens but not in trifoliate orange.These findings provide a comprehensive understanding of citrus root rot and support future research on the mechanisms of root rot resistance in citrus.
基金supported by the National Key R&D Program of China(2018YFA0903200)Science Technology and Innovation Commission of Shenzhen Municipality of China(ZDSYS 20200811142605017)It was also supported by Innovation Program of Chinese Academy of Agricultural Sciences and the Elite Young Scientists Program of CAAS.
摘要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.
基金supported by the National Natural Science Foundation of China(30671266,31101164)the National Basic Research Program of China(2006CB101708,2009CB118404)+2 种基金the National 863 Program of China(2006AA100104)the 111 Project from Ministry of Education of China(B08025)the Youth Science and Technology Innovation Foundation of Nanjing Agriculture University,China(KJ2010002)
摘要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.
摘要Existing studies have challenged the current definition of named bacterial species,especially in the case of highly recombinogenic bacteria.This has led to considering the use of computational procedures to examine potential bacterial clusters that are not identified by species naming.This paper describes the use of sequence data obtained from MLST databases as input for a k-means algorithm extended to deal with housekeeping gene sequences as a metric of similarity for the clustering process.An implementation of the k-means algorithm has been developed based on an existing source code implementation,and it has been evaluated against MLST data.Results point out to potential bacterial clusters that are close to more than one different named species and thus may become candidates for alternative classifications accounting for genotypic information.The use of hierarchical clustering with sequence comparison as similarity metric has the potential to find clusters different from named species by using a more informed cluster formation strategy than a conventional nominal variant of the algorithm.
摘要A computer-aided method to design a hybrid layout--tree-shape planar flowlines is presented. In newtype fiowshop layout, the common machines shared by several flowlines could be located together in functional sections. The approach combines traditional cell formation techniques with sequence alignment algorithms. Firstly, a sequence analysis based cell formation procedure is adopted; then the operation sequences for parts are aligned to maximize machines adjacency in hyperedge representations; finally a tree-shape planar flowline will be obtained for each part family. With the help of a sample of operation sequences obtained from industry, this algorithm is illustrated.
基金supported by the National Key R&D Program of China(2019YFD1001800)the China Agriculture Research System,Overseas Expertise Introduction Project for Discipline Innovation(B18044)+2 种基金the China Agriculture Research System of MOF and MARA(CARS-26-05B)the Natural Science Foundation of Chongqing,China(cstc2019jcyj-msxmX0557)the Guangxi Natural Science Foundation,China(2018GXNSFBA050027)。
摘要In 2009, an emerging citrus viral disease caused by Citrus chlorotic dwarf-associated virus(CCDaV) was discovered in Yunnan Province of China. However, the occurrence and spread of CCDaV in other citrus-growing provinces in China is unknown to date. To better understand the distribution and molecular diversity of CCDaV in China, a total of 1 772 citrus samples were collected from 11 major citrus-growing provinces and were tested for CCDaV by PCR. Among these, 134 citrus samples from Guangxi, Yunnan and Guangdong were tested positive for CCDaV, demonstrating that the occurrence and spread of CCDaV are increasing in China. The complete genome sequences of 17 CCDaV isolates from different provinces and hosts were sequenced. Comparisons of the whole-genome sequences of the 17 CCDaV isolates as well as the 15 isolates available in GenBank revealed that the sequence identity was about 99–100%, showing that the CCDaV isolates were highly conserved. Phylogenetic studies showed that the 32 CCDaV isolates belonged to four different groups based on geographical origins and host species, and that CCDaV isolates from China and Turkey were clustered into different groups. The results provide important information for clarifying the distribution and genetic diversity of CCDaV in China.
基金Supported by National Key Technology Research and Development Program(2006BAD01A1702)~~
摘要[Objective] The aim was to identify genetic variation in Citrus sinensis (sweet orange) germplasm from Hunan Province according to the Start Codon Targeted (SCoT) Polymorphism. [Method] The reaction system for SCoT amplification from sweet orange was first optimized, and then the SCoT fragments were amplified from 24 sweet orange cultivars collected in Hunan Province and sequenced for genetic variation analysis. [Result] The optimum reaction system for SCoT markers amplification was 2.0 μl containing 80 ng of template DNA, 0.3 mmol/L dNTPs, 0.2 μmol/L primer, 1.6 mmol/L Mg2+, 1.6 U of Taq DNA polymerase and 10×PCR buffer. By using this reaction system, the PCR products from the sweet orange cultivars produced clear and reproducible bands at 100-2 000 bp through electrophoresis. The SCoT fragments of the 24 sweet orange cultivars were 1 090-1 091 bp, with the homology of 99.84% and nucleotide deletion and substitution. After being sequenced, the SCoT polymorphisms could distinguish 12 sweet orange cultivars. In addition, the BLAST result showed that part of the SCoT fragments coding region shared high homology with ribosomal protein S3 N superfamily. [Conclusion] This study will provide a theoretical basis for breeding sweet orange cultivars.
摘要Profile hidden Markov models (HMMs) based on classical HMMs have been widely applied for protein sequence identification. The formulation of the forward and backward variables in profile HMMs is made under statistical independence assumption of the probability theory. We propose a fuzzy profile HMM to overcome the limitations of that assumption and to achieve an improved alignment for protein sequences belonging to a given family. The proposed model fuzzifies the forward and backward variables by incorporating Sugeno fuzzy measures and Choquet integrals, thus further extends the generalized HMM. Based on the fuzzified forward and backward variables, we propose a fuzzy Baum-Welch parameter estimation algorithm for profiles. The strong correlations and the sequence preference involved in the protein structures make this fuzzy architecture based model as a suitable candidate for building profiles of a given family, since the fuzzy set can handle uncertainties better than classical methods.
摘要A fundamental goal in cellular signaling is to understand allosteric communication, the process by which sig-nals originating at one site in a protein propagate reliably to affect distant functional sites. The general principles of protein structure that underlie this process remain unknown. Statistical coupling analysis (SCA) is a statistical technique that uses evolutionary data of a protein family to measure correlation between distant functional sites and suggests allosteric communication. In proteins, very distant and small interactions between collections of amino acids provide the communication which can be important for signaling process. In this paper, we present the SCA of protein alignment of the esterase family (pfam ID: PF00756) containing the sequence of antigen 85C secreted by Mycobacterium tuberculosis to identify a subset of interacting residues. Clustering analysis of the pairwise correlation highlighted seven important residue positions in the esterase family alignments. These resi-dues were then mapped on the crystal structure of antigen 85C (PDB ID: 1DQZ). The mapping revealed corre-lation between 3 distant residues (Asp38, Leu123 and Met125) and suggests allosteric communication between them. This information can be used for a new drug against this fatal disease.