Parallel progressive multiple sequence alignment on reconfigurable meshes.

Abstract:

BACKGROUND:One of the most fundamental and challenging tasks in bio-informatics is to identify related sequences and their hidden biological significance. The most popular and proven best practice method to accomplish this task is aligning multiple sequences together. However, multiple sequence alignment is a computing extensive task. In addition, the advancement in DNA/RNA and Protein sequencing techniques has created a vast amount of sequences to be analyzed that exceeding the capability of traditional computing models. Therefore, an effective parallel multiple sequence alignment model capable of resolving these issues is in a great demand. RESULTS:We design O(1) run-time solutions for both local and global dynamic programming pair-wise alignment algorithms on reconfigurable mesh computing model. To align m sequences with max length n, we combining the parallel pair-wise dynamic programming solutions with newly designed parallel components. We successfully reduce the progressive multiple sequence alignment algorithm's run-time complexity from O(m × n4) to O(m) using O(m × n3) processing units for scoring schemes that use three distinct values for match/mismatch/gap-extension. The general solution to multiple sequence alignment algorithm takes O(m × n4) processing units and completes in O(m) time. CONCLUSIONS:To our knowledge, this is the first time the progressive multiple sequence alignment algorithm is completely parallelized with O(m) run-time. We also provide a new parallel algorithm for the Longest Common Subsequence (LCS) with O(1) run-time using O(n3) processing units. This is a big improvement over the current best constant-time algorithm that uses O(n4) processing units.

journal_name

BMC Genomics

journal_title

BMC genomics

authors

Nguyen KD,Pan Y,Nong G

doi

10.1186/1471-2164-12-S5-S4

subject

Has Abstract

pub_date

2011-12-23 00:00:00

pages

S4

issn

1471-2164

pii

1471-2164-12-S5-S4

journal_volume

12 Suppl 5

pub_type

杂志文章
  • Genomic differences between cultivated soybean, G. max and its wild relative G. soja.

    abstract:BACKGROUND:Glycine max is an economically important crop and many different varieties of soybean exist around the world. The first draft sequences and gene models of G. max (domesticated soybean) as well as G. soja (wild soybean), both became available in 2010. This opened the door for comprehensive comparative genomic...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/1471-2164-14-S1-S5

    authors: Joshi T,Valliyodan B,Wu JH,Lee SH,Xu D,Nguyen HT

    更新日期:2013-01-01 00:00:00

  • Genome-wide variation in recombination rate in Eucalyptus.

    abstract:BACKGROUND:Meiotic recombination is a fundamental evolutionary process. It not only generates diversity, but influences the efficacy of natural selection and genome evolution. There can be significant heterogeneity in recombination rates within and between species, however this variation is not well understood outside ...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/s12864-016-2884-y

    authors: Gion JM,Hudson CJ,Lesur I,Vaillancourt RE,Potts BM,Freeman JS

    更新日期:2016-08-09 00:00:00

  • Computational approach to predict species-specific type III secretion system (T3SS) effectors using single and multiple genomes.

    abstract:BACKGROUND:Many gram-negative bacteria use type III secretion systems (T3SSs) to translocate effector proteins into host cells. T3SS effectors can give some bacteria a competitive edge over others within the same environment and can help bacteria to invade the host cells and allow them to multiply rapidly within the ho...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/s12864-016-3363-1

    authors: Hobbs CK,Porter VL,Stow ML,Siame BA,Tsang HH,Leung KY

    更新日期:2016-12-19 00:00:00

  • QTLs associated with dry matter intake, metabolic mid-test weight, growth and feed efficiency have little overlap across 4 beef cattle studies.

    abstract:BACKGROUND:The identification of genetic markers associated with complex traits that are expensive to record such as feed intake or feed efficiency would allow these traits to be included in selection programs. To identify large-effect QTL, we performed a series of genome-wide association studies and functional analyse...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/1471-2164-15-1004

    authors: Saatchi M,Beever JE,Decker JE,Faulkner DB,Freetly HC,Hansen SL,Yampara-Iquise H,Johnson KA,Kachman SD,Kerley MS,Kim J,Loy DD,Marques E,Neibergs HL,Pollak EJ,Schnabel RD,Seabury CM,Shike DW,Snelling WM,Spangler ML,

    更新日期:2014-11-20 00:00:00

  • Introduction to the proceedings of the Avian Genomics and Gene Ontology Annotation Workshop.

    abstract::The Avian Genomics Conference and Gene Ontology Annotation Workshop brought together researchers and students from around the world to present their latest research addressing the delivery of value from the billions of base-pairs of Archosaur sequence that have become available in the last few years. This editorial de...

    journal_title:BMC genomics

    pub_type:

    doi:10.1186/1471-2164-10-S2-I1

    authors: Bridges SM,Burgess SC,McCarthy FM

    更新日期:2009-07-14 00:00:00

  • Cross-species global and subset gene expression profiling identifies genes involved in prostate cancer response to selenium.

    abstract:BACKGROUND:Gene expression technologies have the ability to generate vast amounts of data, yet there often resides only limited resources for subsequent validation studies. This necessitates the ability to perform sorting and prioritization of the output data. Previously described methodologies have used functional pat...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/1471-2164-5-58

    authors: Schlicht M,Matysiak B,Brodzeller T,Wen X,Liu H,Zhou G,Dhir R,Hessner MJ,Tonellato P,Suckow M,Pollard M,Datta MW

    更新日期:2004-08-20 00:00:00

  • GBS-based single dosage markers for linkage and QTL mapping allow gene mining for yield-related traits in sugarcane.

    abstract:BACKGROUND:Sugarcane (Saccharum spp.) is predominantly an autopolyploid plant with a variable ploidy level, frequent aneuploidy and a large genome that hampers investigation of its organization. Genetic architecture studies are important for identifying genomic regions associated with traits of interest. However, due t...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/s12864-016-3383-x

    authors: Balsalobre TW,da Silva Pereira G,Margarido GR,Gazaffi R,Barreto FZ,Anoni CO,Cardoso-Silva CB,Costa EA,Mancini MC,Hoffmann HP,de Souza AP,Garcia AA,Carneiro MS

    更新日期:2017-01-11 00:00:00

  • Correction to: De novo profiling of RNA viruses in Anopheles malaria vector mosquitoes from forest ecological zones in Senegal and Cambodia.

    abstract::Following the publication of this article [1], the authors reported that the original shading in columns 3 and 4 of Table 3, which indicated the presence or absence of viruses in each library, had been removed during typesetting. ...

    journal_title:BMC genomics

    pub_type: 杂志文章,已发布勘误

    doi:10.1186/s12864-019-6067-5

    authors: Belda E,Nanfack-Minkeu F,Eiglmeier K,Carissimo G,Holm I,Diallo M,Diallo D,Vantaux A,Kim S,Sharakhov IV,Vernick KD

    更新日期:2019-09-05 00:00:00

  • Telomere length de novo assembly of all 7 chromosomes and mitogenome sequencing of the model entomopathogenic fungus, Metarhizium brunneum, by means of a novel assembly pipeline.

    abstract:BACKGROUND:More accurate and complete reference genomes have improved understanding of gene function, biology, and evolutionary mechanisms. Hybrid genome assembly approaches leverage benefits of both long, relatively error-prone reads from third-generation sequencing technologies and short, accurate reads from second-g...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/s12864-021-07390-y

    authors: Saud Z,Kortsinoglou AM,Kouvelis VN,Butt TM

    更新日期:2021-01-28 00:00:00

  • Applicability of DNA pools on 500 K SNP microarrays for cost-effective initial screens in genomewide association studies.

    abstract:BACKGROUND:Genetic influences underpinning complex traits are thought to involve multiple quantitative trait loci (QTLs) of small effect size. Detection of such QTL associations requires systematic screening of large numbers of DNA markers within large sample populations. Using pooled DNA on SNP microarrays to screen f...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/1471-2164-8-214

    authors: Docherty SJ,Butcher LM,Schalkwyk LC,Plomin R

    更新日期:2007-07-04 00:00:00

  • Identification and evaluation of PCR reference genes for host and pathogen in sugarcane-Sporisorium scitamineum interaction system.

    abstract:BACKGROUND:Sugarcane (Saccharum L. plant) is an important crop for sugar and bio-energy production around the world. Among sugarcane diseases, smut caused by Sporisorium scitamineum is one of the major fungal diseases causing severe losses to the sugarcane industry. The use of PCR reference genes is essential to the no...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/s12864-018-4854-z

    authors: Huang N,Ling H,Liu F,Su Y,Su W,Mao H,Zhang X,Wang L,Chen R,Que Y

    更新日期:2018-06-19 00:00:00

  • Evidence of uneven selective pressure on different subsets of the conserved human genome; implications for the significance of intronic and intergenic DNA.

    abstract:BACKGROUND:Human genetic variation produces the wide range of phenotypic differences that make us individual. However, little is known about the distribution of variation in the most conserved functional regions of the human genome. We examined whether different subsets of the conserved human genome have been subjected...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/1471-2164-10-614

    authors: Davidson S,Starkey A,MacKenzie A

    更新日期:2009-12-16 00:00:00

  • Database of exact tandem repeats in the Zebrafish genome.

    abstract:BACKGROUND:Sequencing of the approximately 1.7 billion bases of the zebrafish genome is currently underway. To date, few high resolution genetic maps exist for the zebrafish genome, based mainly on single nucleotide polymorphisms (SNPs) and short microsatellite repeats. The desire to construct a higher resolution genet...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/1471-2164-11-347

    authors: Rouchka EC

    更新日期:2010-06-01 00:00:00

  • A manually annotated Actinidia chinensis var. chinensis (kiwifruit) genome highlights the challenges associated with draft genomes and gene prediction in plants.

    abstract:BACKGROUND:Most published genome sequences are drafts, and most are dominated by computational gene prediction. Draft genomes typically incorporate considerable sequence data that are not assigned to chromosomes, and predicted genes without quality confidence measures. The current Actinidia chinensis (kiwifruit) 'Hongy...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/s12864-018-4656-3

    authors: Pilkington SM,Crowhurst R,Hilario E,Nardozza S,Fraser L,Peng Y,Gunaseelan K,Simpson R,Tahir J,Deroles SC,Templeton K,Luo Z,Davy M,Cheng C,McNeilage M,Scaglione D,Liu Y,Zhang Q,Datson P,De Silva N,Gardiner SE,Bas

    更新日期:2018-04-16 00:00:00

  • Parallel selection on gene copy number variations through evolution of three-spined stickleback genomes.

    abstract:BACKGROUND:Understanding the genetic basis of adaptive evolution is one of the major goals in evolutionary biology. Recently, it has been revealed that gene copy number variations (GCNVs) constitute significant proportions of genomic diversities within natural populations. However, it has been unclear whether GCNVs are...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/1471-2164-15-735

    authors: Hirase S,Ozaki H,Iwasaki W

    更新日期:2014-08-29 00:00:00

  • Systems perspectives on erythromycin biosynthesis by comparative genomic and transcriptomic analyses of S. erythraea E3 and NRRL23338 strains.

    abstract:BACKGROUND:S. erythraea is a Gram-positive filamentous bacterium used for the industrial-scale production of erythromycin A which is of high clinical importance. In this work, we sequenced the whole genome of a high-producing strain (E3) obtained by random mutagenesis and screening from the wild-type strain NRRL23338, ...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/1471-2164-14-523

    authors: Li YY,Chang X,Yu WB,Li H,Ye ZQ,Yu H,Liu BH,Zhang Y,Zhang SL,Ye BC,Li YX

    更新日期:2013-07-31 00:00:00

  • Elimination of PCR duplicates in RNA-seq and small RNA-seq using unique molecular identifiers.

    abstract:BACKGROUND:RNA-seq and small RNA-seq are powerful, quantitative tools to study gene regulation and function. Common high-throughput sequencing methods rely on polymerase chain reaction (PCR) to expand the starting material, but not every molecule amplifies equally, causing some to be overrepresented. Unique molecular i...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/s12864-018-4933-1

    authors: Fu Y,Wu PH,Beane T,Zamore PD,Weng Z

    更新日期:2018-07-13 00:00:00

  • Analyzing adjuvant radiotherapy suggests a non monotonic radio-sensitivity over tumor volumes.

    abstract:BACKGROUND:Adjuvant Radiotherapy (RT) after surgical removal of tumors proved beneficial in long-term tumor control and treatment planning. For many years, it has been well concluded that radio-sensitivities of tumors upon radiotherapy decrease according to the sizes of tumors and RT models based on Poisson statistics ...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/1471-2164-9-S2-S9

    authors: Yang JY,Niemierko A,Yang MQ,Deng Y

    更新日期:2008-09-16 00:00:00

  • A kingdom-specific protein domain HMM library for improved annotation of fungal genomes.

    abstract:BACKGROUND:Pfam is a general-purpose database of protein domain alignments and profile Hidden Markov Models (HMMs), which is very popular for the annotation of sequence data produced by genome sequencing projects. Pfam provides models that are often very general in terms of the taxa that they cover and it has previousl...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/1471-2164-8-97

    authors: Alam I,Hubbard SJ,Oliver SG,Rattray M

    更新日期:2007-04-10 00:00:00

  • RBM6-RBM5 transcription-induced chimeras are differentially expressed in tumours.

    abstract:UNLABELLED:Transcription-induced chimerism, a mechanism involving the transcription and intergenic splicing of two consecutive genes, has recently been estimated to account for approximately 5% of the human transcriptome. Despite this prevalence, the regulation and function of these fused transcripts remains largely un...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/1471-2164-8-348

    authors: Wang K,Ubriaco G,Sutherland LC

    更新日期:2007-10-01 00:00:00

  • Single nucleotide polymorphism discovery from expressed sequence tags in the waterflea Daphnia magna.

    abstract:BACKGROUND:Daphnia (Crustacea: Cladocera) plays a central role in standing aquatic ecosystems, has a well known ecology and is widely used in population studies and environmental risk assessments. Daphnia magna is, especially in Europe, intensively used to study stress responses of natural populations to pollutants, cl...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/1471-2164-12-309

    authors: Orsini L,Jansen M,Souche EL,Geldof S,De Meester L

    更新日期:2011-06-13 00:00:00

  • Comparative transcriptomic analysis unveils interactions between the regulatory CarS protein and light response in Fusarium.

    abstract:BACKGROUND:The orange pigmentation of the agar cultures of many Fusarium species is due to the production of carotenoids, terpenoid pigments whose synthesis is stimulated by light. The genes of the carotenoid pathway and their regulation have been investigated in detail in Fusarium fujikuroi. In this and other Fusarium...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/s12864-019-5430-x

    authors: Ruger-Herreros M,Parra-Rivero O,Pardo-Medina J,Romero-Campero FJ,Limón MC,Avalos J

    更新日期:2019-01-21 00:00:00

  • Accurate single nucleotide variant detection in viral populations by combining probabilistic clustering with a statistical test of strand bias.

    abstract:BACKGROUND:Deep sequencing is a powerful tool for assessing viral genetic diversity. Such experiments harness the high coverage afforded by next generation sequencing protocols by treating sequencing reads as a population sample. Distinguishing true single nucleotide variants (SNVs) from sequencing errors remains chall...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/1471-2164-14-501

    authors: McElroy K,Zagordi O,Bull R,Luciani F,Beerenwinkel N

    更新日期:2013-07-24 00:00:00

  • AvBD1 nucleotide polymorphisms, peptide antimicrobial activities and microbial colonisation of the broiler chicken gut.

    abstract:BACKGROUND:The importance of poultry as a global source of protein underpins the chicken genome and associated SNP data as key tools in selecting and breeding healthy robust birds with improved disease resistance. SNPs affecting host peptides involved in the innate defences tend to be rare, but three non-synonymous SNP...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/s12864-017-4034-6

    authors: Cadwell K,Niranji SS,Armstrong VL,Mowbray CA,Bailey R,Watson KA,Hall J

    更新日期:2017-08-18 00:00:00

  • Enhanced sugar accumulation and regulated plant hormone signalling genes contribute to cold tolerance in hypoploid Saccharum spontaneum.

    abstract:BACKGROUND:Wild sugarcane Saccharum spontaneum plants vary in ploidy, which complicates the utilization of its germplasm in sugarcane breeding. Investigations on cold tolerance in relation to different ploidies in S. spontaneum may promote the exploitation of its germplasm and accelerate the improvement of sugarcane va...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/s12864-020-06917-z

    authors: Yang H,Wang T,Yu X,Yang Y,Wang C,Yang Q,Wang X

    更新日期:2020-07-22 00:00:00

  • Genome-wide analysis of the WRKY gene family and their positive responses to phytoplasma invasion in Chinese jujube.

    abstract:BACKGROUND:The WRKY gene family is one of the most important families in higher plants. As transcription factors, they actively respond to biotic and abiotic stress and are also involved in plant development. Chinese jujube (Ziziphus jujuba Mill.) is the largest type of dried fruit tree in China in terms of production,...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/s12864-019-5789-8

    authors: Xue C,Li H,Liu Z,Wang L,Zhao Y,Wei X,Fang H,Liu M,Zhao J

    更新日期:2019-06-07 00:00:00

  • Contrasting gene expression patterns in grain of high and low asparagine wheat genotypes in response to sulphur supply.

    abstract:BACKGROUND:Free asparagine is the precursor for acrylamide formation during cooking and processing of grains, tubers, beans and other crop products. In wheat grain, free asparagine, free glutamine and total free amino acids accumulate to high levels in response to sulphur deficiency. In this study, RNA-seq data were ac...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/s12864-019-5991-8

    authors: Curtis TY,Raffan S,Wan Y,King R,Gonzalez-Uriarte A,Halford NG

    更新日期:2019-08-01 00:00:00

  • Comparing Mycobacterium tuberculosis genomes using genome topology networks.

    abstract:BACKGROUND:Over the last decade, emerging research methods, such as comparative genomic analysis and phylogenetic study, have yielded new insights into genotypes and phenotypes of closely related bacterial strains. Several findings have revealed that genomic structural variations (SVs), including gene gain/loss, gene d...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/s12864-015-1259-0

    authors: Jiang J,Gu J,Zhang L,Zhang C,Deng X,Dou T,Zhao G,Zhou Y

    更新日期:2015-02-14 00:00:00

  • Generation and analysis of expression sequence tags from haustoria of the wheat stripe rust fungus Puccinia striiformis f. sp. Tritici.

    abstract:BACKGROUND:Stripe rust, caused by Puccinia striiformis f. sp. tritici (Pst), is one of the most destructive diseases of wheat (Triticum aestivum L.) worldwide. In spite of its agricultural importance, the genomics and genetics of the pathogen are poorly characterized. Pst transcripts from urediniospores and germinated ...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/1471-2164-10-626

    authors: Yin C,Chen X,Wang X,Han Q,Kang Z,Hulbert SH

    更新日期:2009-12-23 00:00:00

  • Structured RNAs and synteny regions in the pig genome.

    abstract:BACKGROUND:Annotating mammalian genomes for noncoding RNAs (ncRNAs) is nontrivial since far from all ncRNAs are known and the computational models are resource demanding. Currently, the human genome holds the best mammalian ncRNA annotation, a result of numerous efforts by several groups. However, a more direct strateg...

    journal_title:BMC genomics

    pub_type: 杂志文章

    doi:10.1186/1471-2164-15-459

    authors: Anthon C,Tafer H,Havgaard JH,Thomsen B,Hedegaard J,Seemann SE,Pundhir S,Kehr S,Bartschat S,Nielsen M,Nielsen RO,Fredholm M,Stadler PF,Gorodkin J

    更新日期:2014-06-10 00:00:00