Image Registration Using Implicit Similarity and Pixel Migration

BRIG0.95ManualNabil AlikhanJune27,2011/projects/brig/1CONTENTS2 Contents1Introduction3 2Licence9 3Installation93.1Installing BLAST (9)4Warning when using BLAST114.1Low complexityfiltering (11)4.2Expected values(e-values)and bit scores (11)5Visualising whole genome comparisons135.1Step1:Load in sequences (13)5.2Step2:Configure rings (14)5.3Step3:Review and submit (16)6Working with a Multi-FASTA reference186.1Step1:Load in sequences (18)6.2Step2:Configure rings,annotations and spacer value (19)6.3Step3:Configure image settings and submit (23)7Visualising graphs and genome assemblies257.1Walkthrough for visualising SAMfile mapping coverage (26)7.2Walk through for visualising acefile assembly coverage (31)8Walkthroughs on creating custom annotations398.1Adding custom annotations from a tab-delimitedfile,GenBank orEMBLfile (39)8.1.1Step1:Load in sequences (39)8.1.2Step2:Configure rings (40)8.1.3Step3:Adding annotations (41)8.1.4Step4:Review and submit (43)8.2How to create tab-delimitedfiles for BRIG (45)9Configuration options469.1Saving and reopening your work (46)9.2BLAST options (46)9.3Setting BRIG options (48)9.4Setting Image options (50)9.5Loading a preset image template (52)1INTRODUCTION3 1IntroductionThe BLAST Ring Image Generator(BRIG)is a cross-platform desktop applica-tion written in Java1.6.It uses CGView[5]for image rendering and the Basic Local Alignment Search Tool(BLAST)for genome comparisons.It has a graph-ical user interface programmed on the Swing framework,which takes the user step-by-step through the configuration of a circular image generation.Figure1is an example of an image BRIG can create.Figure1:BRIG example output image of a simulated draft E.coli O157:H7 genome.Thefigure show BLAST comparisons against28published E.coli and Salmonella genomes against the simulated draft genome.1INTRODUCTION4 Figure2shows a magnified view of the same example image showing similar-ity between a central reference genome in the centre against other query sequences as a set of concentric rings,where colour indicates a BLAST match of a particular percentage identity.BRIG does not represent sequences that are not present in the reference genome The image shows:•GC skew,•GC content,•Genome coverage and contig boundaries(calculated from an assemblyfile),•Genome alignment results,customs annotations.Figure2:A magnified view of BRIG example image1INTRODUCTION5 How to use this manualThis manual contains a set of detailed walk throughs where readers are taken step by step through a worked example.Each walkthrough highlights different features of BRIG and users should work through each one.If you are interested in a particular aspect of BRIG,please turn to the relevant walkthrough:•Whole genome comparisons,including how to load in coverage graphs,e.g.Figures1&3,see Section5on page13.•Using a user-defined list of genes as a reference(in Multi-FASTA),e.g Fig-ure4,see Section6on page18.•Creating and visualising graphs generated from assembly(.ace)or read mapping coverage(.SAM),e.g Figure5,see Section7on page25.•Labeling images with information from GenBank,Tab-delimited or Multi-FASTAfiles,like those seen in Figure3,4&5,see Section8on page39.The manual also has detailed instructions for how to install and configure BRIG:•For instructions on how to install BRIG,see Section3on page9.•For instructions on how to configure BRIG and save BRIG settings,see Section9on46.1INTRODUCTION6Figure3:Reference:Published E.coli O157:H7Sakai genome.Query:Com-plete genome sequences of related strains,listed in the key.The prophage regions from the Sakai genome are marked in alternating black&blue.To make an image like this please refer to Section5on page13.1INTRODUCTION7Figure4:Reference:A list of translated genes that make up the Locus of Entero-cyte Effacement(LEE),which encodes a Type III secretion system.Query:Raw sequencing reads simulated from several complete LEE+published genomes(nu-cleotide sequence)and E.coli K12,(negative control;LEE-).You can clearly see gene presence/absence,and divergence(the colour represents sequence identity on a sliding scale,the greyer it gets;the lower the percentage identity).To make an image like this please refer to Section6on page18.1INTRODUCTION8Figure5:Reference:Published E.coli O157:H7Sakai genome.Query:Read mapping coverage of sequencing reads simulated from complete genomes,indi-cated in the key.Simulated sequencing reads were mapped onto the published complete Sakai genome using BWA.The read coverage for each genome was generated from the resulting SAMfipare this with Figure3,which is based on the original published genome sequences.To make an image like this please refer to Section7on page25.2LICENCE9 2LicenceThis program is free software:you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foun-dation,either version3of the License,or(at your option)any later version.This program is distributed in the hope that it will be useful,but without any warranty;without even the implied warranty of merchantability orfitness for a particular purpose.See the GNU General Public License for more details.You should have received a copy of the GNU General Public License along with this program.If not,see</licenses/>.Please note that these restrictions do not apply to the third party libraries bundled with this software.3InstallationThere’s no real”Installation”process for BRIG itself.However,BLAST+[2]or BLAST legacy[1]must already be installed and BRIG needs to be able to locate the BLAST executables(See Section3.1).To run BRIG users need to:1.Download the latest version(BRIG-x.xx-dist.zip)from/projects/brig/2.Unzip BRIG-x.xx-dist.zip to a desired location.3.Run BRIG.jar,by double clicking.Users who wish to run BRIG from the command-line need to:1.Navigate to the unpacked BRIG folder in a command-line interface(termi-nal,console,command prompt).2.Run“java-Xmx1500M-jar BRIG.jar”.Where-Xmx specifies the amountof memory allocated to BRIG.3.1Installing BLASTThe latest version of BLAST+[2]can be downloaded from:ftp:///blast/executables/blast+/LATEST/ BLAST+offers a number of improvements on the original BLAST implementa-tion and comes as a bundled installer,which will walk users through the installa-tion process.Please read the published paper on BLAST+:3INSTALLATION10 Camacho,C.,G.Coulouris,et al.(2009).“BLAST+:architecture and appli-cations.”BMC Bioinformatics10(1):421Available online at:http://www. /1471-2105/10/421The latest version of BLAST legacy[1]can be downloaded from:ftp:///blast/executables/release/LATEST/ BLAST legacy comes as a compressed package,which will unzip the BLAST binaries where ever the package is.We advise users tofirst create a BLAST direc-tory(in either the home or applications directory),copy the downloaded BLAST package to that directory and unzip the package.BRIG supports both BLAST+&BLAST ers can specify the loca-tion of their BLAST installation in the BRIG options menu which is: Main window>Preferences>BRIG options.The window is shown in Figure6.If BRIG cannotfind BLAST it will prompt users at runtime.PRO TIP1:BRIG uses BLAST,do not use wwwblast or netblast with BRIG. PRO TIP2:If BOTH BLAST+and legacy versions are in the same location, BRIG will prefer BLAST+.Figure6:You can change where BRIG looks for BLAST in the BRIG options window.For more information about BRIG options see Section9.2on page48.4W ARNING WHEN USING BLAST11 4Warning when using BLASTBRIG relies on the Basic Local Alignment Search Tool(BLAST)for genome comparisons.BLAST has a number of behaviours that may seem counterintuitive and we encourage users to learn about local alignment and the BLAST algorithm to fully understand the images that BRIG produces.There are a few concepts to keep in mind when using BRIG:4.1Low complexityfilteringPRO TIP3:BLASTfilters may cause gaps in alignments,which will show up as blank regions in BRIG images.BLASTfilters(BLAST legacy-Fflag or BLAST+-dust/-seg noflag)filter the query sequence for low-complexity sequences by default.This includes sequences that are highly repetitive or contain the same nucleotide for long lengths of the sequences.Low-complexityfiltering is generally a good idea,but it may break long matches into several smaller matches.This is often shown in BRIG images as truncations or gaps in alignments,it is particularly obvious in very small reference sequences where alignments are shown on a gene-by-gene level.To prevent this,either turn offfiltering or use soft masking.4.2Expected values(e-values)and bit scoresPRO TIP4:BLAST’s bitscorefiltering may cause different results in BRIG if users swap the query and reference sequences,particularly if these are very different sizes.BLAST uses statistical thresholds tofilter out“bad alignments”;alignment matches that appear random to BLAST.One of these thresholds is the e-value,which is the probability of the alignment occurring by chance,given the complexity of the match,sequence composition and the size of the database.It is more likely in a larger sequence that an alignment could occur by chance,so BLAST is more critical of these matches.This can create different expected values if BLAST is used with the same reference sequence against databases of different sizes and may potentiallyfilter out significant matches or include poor scoring ones.4W ARNING WHEN USING BLAST12 Because of this,users might notice different results in BRIG images if they swap the order of the database and reference sequences around in the BLAST, especially if the two sequences are quite different in size.The differences are often due to a few very low-scoring hits.Users should consider what an appropriate e-value threshold is for the compar-isons that they run.Remember,that BLAST runs with an e-value of10by default, we recommend that users change this ers can set thefinal threshold (e-value)with the-eflag in BLAST legacy or-evalueflag in BLAST+.PRO TIP5:BLAST does not handle spaces infilenames,BRIG will prompt users if they have spaces infile locations.5VISUALISING WHOLE GENOME COMPARISONS135Visualising whole genome comparisonsIn this section we will walk through the basics of generating an image.This walk through will be comparing an E.coli genome withfive other E.coli genomes and mapping the read coverage from the underlying genome assembly onto the same image.For this walk through,users will need BRIG examples.zip,which is avail-able from the BRIG website(/projects/brig/ files/).This contains all the genomes andfiles needed to follow along with this walk through.Unzip it somewhere easily accessible,like the home directory or desktop.About the reference genomeThe reference genome used in this walk through is a simulated E.coli genome assembly.We took the published E.coli O157:H7Sakai genome(Accession num-ber BA000007)sequence and had assembly reads simulated by METASIM[4]and then assembled these using Newbler version2.3.The resulting contiguous se-quences were ordered using Mauve[3]against the published Sakai genome.This simulated E.coli is useful for illustrating some of BRIG’s graphing features for assembly read coverage.Enterohemorrhagic E.coli are gram-negative,enteric bacterial pathogens.They can cause diarrhea,hemorrhagic colitis,and hemolytic uremic syndrome.This particular genome we are using in this example was based on an E.coli O157:H7 isolated from the Sakai,Japan outbreak.5.1Step1:Load in sequencesThe walk through will work out of the unzipped BRIG examples.zip in the Chap-ter568wholeGenomeExamples folder.The walk through and relatedfigureswill use C:\BRIG examples\Chapter568wholeGenomeExamples as that loca-tion.To keep thefinal image consistent with the walk through,please open”Exam-pleProfile.xml”from the Chapter568wholeGenomeExamples folder.Thisfile configures BRIG to the same image settings in the walk through.1.First,set BRIGExample.fna as the reference sequence.2.Set<unzipped BRIG examples folder>\Chapter568wholeGenomeExamplesas the query sequence folder.3.Press“add to data pool”,this should load several items into the pool list,there should be ninefiles.5VISUALISING WHOLE GENOME COMPARISONS144.Set the Chapter568wholeGenomeExamples as the output folder.5.The BLAST options box should be left blank.6.Click nextPRO TIP6:Users can add individualfiles to the data pool too.5.2Step2:Configure ringsThe next step is to configure what information is shown on each of the concentric rings in BRIG.Create six rings,for each ring:1.Set the legend text for each ring2.Select the required sequences from the data pool and click on“add data”toadd to the ring list.3.Choose a colour4.Set the upper(90)and lower(70)identity threshold.5VISUALISING WHOLE GENOME COMPARISONS155.Click on“add new ring”and repeat steps for each new ring required.The values required for each ring are detailed in the table below.Notice that thatsequences can be collated into a single ring,like the example of K12&HS.The ring will show BLAST matches from both HS and K12.Legend text Required sequences ColourGC Content GC Content IgnoreGC Skew GC Skew IgnoreCoverage BRIGExample.graph153,0,0O157:H7E coli O157H7Sakai.gbk0,0,153HS and K12E coli HS.fna0,153,0E coli K12MG1655.fnaCFT073and UTI89E coli CFT073.fna153,0,153E coli UTI89.fna5VISUALISING WHOLE GENOME COMPARISONS16 PRO TIP7:Rings can be reordered by dragging them in the Ring List pane. PRO TIP8:You can set default threshold values in“BRIG options”.See section9.2(page48)for more details.PRO TIP9:When using a Genbank/EMBLfile as a reference,users can choose whether to use the protein or nucleotide sequence.5.3Step3:Review and submitThe last window allows us to change the BLAST options,the location of the imagefile and set the image title,which will appear in the centre of the ring.For the walkthrough configure the third window as:1.Set the image title as“BRIG example image”.2.Hit submit.3.The image will be created in the specified output directory and should looksomething like Figure7.BRIG will format Genbankfiles,run BLAST,parse the results and render the im-age.Thefinal image(Figure7)shows GC Content and Skew,the Genome cover-age,contig boundaries,and the BLAST results against the other E.coli genomes. The results for HS and K12have been collated into a single ring,likewise for UTI89and CFT073.5VISUALISING WHOLE GENOME COMPARISONS17Figure7:Thefinal BRIG imagePRO TIP10:Image settings,like size,fonts,etc can be configured in:Main window>Preferences>Image options..6WORKING WITH A MULTI-FASTA REFERENCE186Working with a Multi-FASTA reference6.1Step1:Load in sequencesThis section is a walk through of how to use BRIG to generate an image using a listof genes in Multi-FASTA format as a reference.The multi-FASTAfile in this ex-ample is a number of virulence genes from enterohemorrhagic and uropathogenic E.coli,which includes EHEC polarfimbraie(ecpA to ecpR),EHEC Locus of En-terocyte Effacement(espF to espG)and the UPEC F1C Fimbraie(focA to focI), which will be compared against the whole genome seqeuences of E.coli strainsO157:H7Sakai,K12MG1665,O126:H7and CFT073.Start a new session in BRIG and load in thefiles from the Chapter568wholeGenomeExamples folderin the unzipped BRIG-Example folder:1.Set the reference sequence as“Ecoli vir.fna”.Users can use the browsebutton to traverse thefile system.2.Set<unzipped BRIG examples folder>/Chapter568wholeGenomeExamplesas the query sequence folder.3.Press“add to data pool”,this should load several items into the pool list.4.Set the output folder as unzipped BRIG-Example folder.5.Make sure the BLAST options box is blank.6.Click“Next”.6WORKING WITH A MULTI-FASTA REFERENCE196.2Step2:Configure rings,annotations and spacer valueThe next step is to configure what information is shown on each concentric ring in BRIG.Figure8is an example of how one of the windows should be set up.There should befive rings.Do the follow for each ring,according to the table below:1.Set legend text for each ring.2.Select the required sequences from the data pool and click“add data”toadd.3.Choose a colour4.Set upper(90)and lower(70)identity thresholds.5.Click“add new ring”and repeat these steps for each new ring.Legend text Required sequences ColourO157:H7E coli O157H7Sakai.gbk172,14,225O126:H7E coli O126.fna255,0,51CFT073E coli CFT073.fna0,0,102K12E coli K12MG1655.fna161,221,231null none ignoreAfter each ring is configured,users need to make the following changes:1.Set the spacerfield to50base pairs.2.Set the ring size of ring5as“2”.PRO TIP11:The Spacerfield determines the number of base pairs to leave between FASTA sequences.The next step is to add the gene annotations,which will be fetched from the Multi-FASTA headers:1.Click Add custom features in the second BRIG window to bring up customannotation window(Figure9).2.Double click“Ring5”.3.Set“input data”as Multi-FASTA.4.Set“colour”as alternating red-blue5.Click add.6WORKING WITH A MULTI-FASTA REFERENCE20Figure8:Ring set-up for Multi-FASTAfile6WORKING WITH A MULTI-FASTA REFERENCE21Figure9:Custom annotation window-adding gene annotations6WORKING WITH A MULTI-FASTA REFERENCE22 This step colours the gaps between FASTA entries,the gaps are calculated from the Multi-FASTAfile(Figure10).For each genome ring,do the following:1.Set“input data”as Multi-FASTA.2.Set“colour”as black3.Check“load gaps only”.4.Click add.The results should be similar to Figure10in the left hand pane.Close the window when this is done.PRO TIP12:A spacer value can be set when using protein sequences from a Genbank/EMBLfile.Figure10:Custom annotation window-adding spacers6WORKING WITH A MULTI-FASTA REFERENCE236.3Step3:Configure image settings and submitThere are a few more steps to complete and then the image isfinished.In the customize ring window:1.Make the following changes in Preferences>Image options(a)Set“show shading”in“Global settings”as false.(b)Set“featureSlot”spacing in“Feature settings”as x-small.2.Return to customize ring window,click“Next”to go to thefinal BRIGconfirmation window3.Set the image title as“Various E.coli virulence genes”and press submit. The output image should be something like Figure11.The alternating red-blue op-tion has automatically alternated the red and blue colours for the gene labels.This option is available whenever a multi-FASTAfile is used as a reference sequence. This same option could be used to show contig or genome scaffold boundaries. This image shows some real biological information very clearly.1.CFT073(UPEC)and K12MG1655(Commensal)do not carry the Locus ofEnterocyte Effacement.These virulence factors are specific to EHEC and EPEC.2.All E.coli shown carry the common pilus(ecpA-R).3.Only CFT073carries the F1Cfimbriae.PRO TIP13:You use protein sequences as a multi-FASTA reference and use blastx to improve alignment accuracy for divergent sequences.6WORKING WITH A MULTI-FASTA REFERENCE24Figure11:Output image from Multi-FASTA walkthrough.This was generated using BLAST+[2],BLAST legacy[1]will produce slightly different results.7VISUALISING GRAPHS AND GENOME ASSEMBLIES25 7Visualising graphs and genome assembliesBRIG can produce any user-specified graph e.g coverage,read mapping,expres-sion data etc.For example,the coverage graph in Figure2was produced from a tab-delimited textfile,with a start,stop and value for that range.BRIG supports.acefiles(produced by Newbler,454/Roche’s propriety as-sembler,and used by PHRAP/Consed)or SAMfiles(used for read mapping and some de-novo assemblers).BRIG has a number of modules for handling assembly information.These tools are:•Contig mapping:BRIG will use BLAST to try and map contigs from an .ace or Multi-FASTAfile onto a reference genome and produce a.graphfile that can show frequency of BLAST hits and the best BLAST hit position of contigs.It will then produce a.graphfile of the frequency of BLAST hits and the best BLAST hit position of contigs and another.graphfile,with the suffix”rep.graph”showing all the other BLAST hits.•Coverage graph:BRIG requires an.ace or.samfile and an output loca-tion(Figure7.1).BRIG will calculate coverage values over a user-defined window and produce a.graphfile in the output folder.This will create a tab-delimited.graphfile,which can be loaded into back BRIG.•Convert graph:A draft genome is usually modified post assembly;adding spacers,reordering contigs,etc.These changes are often not reflected in the original.acefiles BRIG uses to generate coverage graphs.BRIG can use BLAST to align the original assembly output with the newer sequence and map the coverage information to the new sequence.BRIG requires:–Original454AllContigs.fna produced by Newbler.–Graphfile created by BRIG’s“Coverage graph”module,based onNewbler’s acefile.–The modified sequence or another suitable reference genome.BRIG will produce a new.graphfile in the output folder,using thefilename of the originalfile,with“new.graph”appended to the end.To create work with graphfiles:Main window>Modules>Create graphfiles Using graphfiles in BRIG images.graphfiles should visible when users load a directory into the query sequence pool(Figure7.1).Graphs can be treated like any other sequencefile in BRIG;the example from Figure7.1shows a graphfile loaded into thefirst ring of a particular BRIG session.7VISUALISING GRAPHS AND GENOME ASSEMBLIES26 PRO TIP14:Graphfiles cannot be shown on same ring as sequencefiles (protein or nucleotide).7.1Walkthrough for visualising SAMfile mapping coverage. This section will give a worked example of producing a BRIG image show-ing mapping reads coverage from a SAM inputfile.Thefinal image will look like Figure12.This walkthrough requires BRIG examples.zip from the BRIG website(/projects/brig/files/).Unzip this somewhere convenient.The general procedure is tofirst generate the graphfiles from the SAMfile,add additionalfiles to data pool,edit the rings and annotation, then render the image.1.Open a new BRIG session.2.Create the graphfile from the graphfiles modules:Main window>Mod-ules>Create graphfiles.(a)Set drop down to coverage graph,fill infields(Figure7.1).(b)Set Assemblyfile as“Mu50.sam”from the BRIG examples/Chapter7-sam-examples folder.(c)Set Output folder as the location of the Chapter7-sam-examples folder.(d)Window size as“1”..(e)Click Create Graph.This will add the graphfile to the data pool whenit hasfinished.7VISUALISING GRAPHS AND GENOME ASSEMBLIES27Close the coverage graph window and return to thefirst main window.1.Set referencefile as“S.aureus.Mu50-plasmid-AP003367.gbk”from the Chapter7-sam-examples ers can use the browse button to traverse thefilesystem.2.Set<unzipped BRIG examples folder>/Chapter7-sam-examples as the querysequence folder.3.Press“add to data pool”,this should load several items into the pool list.4.Set the output folder as unzipped Chapter7-sam-examples folder.5.Make sure the BLAST options box is blank.Click next to move to the next window to configure the rings and add in annota-tions.1.Create4rings,name them“Mapping Coverage”,“pSK57”,“SAP014A”,“CDS”.2.Ring1Settings:(a)Add“Mu50.sam.graph”from data pool to Ring1.(b)Set graph maximum value as“10”.(c)Set colour as rgb(204,0,0).(d)Set legend title as“Mapping coverage”.(e)Check show red/blue.7VISUALISING GRAPHS AND GENOME ASSEMBLIES283.Ring2Settings:(a)Add“S.aureus.pSK57-plasmid-GQ900493.gbk”from data pool to Ring2.(b)Set colour as rgb(0,0,102).(c)Set legend title as“pSK57”.4.Ring3Settings:(a)Add“S.aureus.SAP014A-plasmid-GQ900379”from data pool to Ring3.(b)Set colour as rgb(102,0,102).(c)Set legend title as“SAP014A”.5.Ring4Settings:(a)Set colour as rgb(0,0,0).(b)Set legend title as“CDS”.7VISUALISING GRAPHS AND GENOME ASSEMBLIES29Click“Add Custom features”.1.Double-click Ring4.2.Set Input data to“Genbank”.3.Set colour to“black”.4.Set Draw feature as“default”.5.Set Genbankfile location to the location of“S.aureus.Mu50-plasmid-AP003367.gbk”.6.Set Feature as“CDS”7.Click add.This will load all the coding sequences from the Genbankfile.These annotations will be drawn as arrows,indicating orientation.Close this window and click next on the second window.1.Set title as“S.aureus Mu50plasmid”.2.Click Submit.This will generate thefinal image,it should look like Figure12.7VISUALISING GRAPHS AND GENOME ASSEMBLIES30Figure12:S.aureus Mu50plasmid,showing read mapping from simulated454 reads,CDSs,and genome comparisons to other S.aureus plasmids,pSK57& SAP014A.Alignments were performed with BLAST+7VISUALISING GRAPHS AND GENOME ASSEMBLIES317.2Walk through for visualising acefile assembly coverage. This section will give a worked example of producing a BRIG image showing assembly coverage read from an acefile.Thefinal image will look like Fig-ure13.This walk through requires BRIG examples.zip from the BRIG website (/projects/brig/files/).Unzip this some-where convenient.The general procedure is tofirst generate the graphfiles from the acefile,con-vert the coverage information to reference sequence if necessary,add additional files to data pool,edit rings and annotation,then render the image.Draft genome sequences are often modified to be consistant with other infor-mation(e.g genome scaffolding,PCR sequencing of gaps)after being initially assembled.This may change the order and size of thefinal genome sequence compared to the original assembly.To show the read coverage from the assembly on thefinal sequence correctly the“Convert graph”module within BRIG can be used to map the coverage infor-mation from the acefile onto the new sequence.This module can also be used to map read coverage from an assembly onto a closely-related reference genome.7VISUALISING GRAPHS AND GENOME ASSEMBLIES32First,produce the coverage graphfile based off the assembly(acefile):1.Open a new BRIG session.2.Create the graphfile from the graphfiles module:Main window>Modules>Create graphfiles.3.Set drop down to coverage graph,fill infields(Figure7.2).(a)Set Assemblyfile as“454-S.aureus.Mu30.ace”from the BRIGEXAMPLE2-ace folder.(b)Set Output folder as the location of the BRIGEXAMPLE2-ace folder.(c)Set window size as“1”.4.Click“Create Graph”.This will add the graphfile to the data pool when ithasfinished.7VISUALISING GRAPHS AND GENOME ASSEMBLIES33 Next,map the coverage generated in the previous graphfile to the modified genome sequence.1.Remain in the“Create custom graph”window:Main window>Modules>Create graphfiles.2.Set drop down to convert graph,fill infields as below.(a)Set Original sequence as“454AllContigs-S.aureus.Mu50.fna”.(b)Set New sequence as“S.aureus.Mu50-plasmid-AP003367.fna”.(c)Set graphfile as“454-S.aureus.Mu50.ace.graph”.(d)Set Output folder as the location of the BRIGEXAMPLE2-ace folder.(e)Window size as“1”.3.Click“Create Graph”.This will add the graphfile to the data pool when ishasfinished.7VISUALISING GRAPHS AND GENOME ASSEMBLIES34Close the“Create custom graph”window and return to the main window.1.Set referencefile as“S.aureus.Mu50-plasmid-AP003367.gbk”from theBRIGEXAMPLE2-ace ers can use the browse button to traverse thefile system.2.Set<unzipped BRIGEXAMPLE2-ace folder>/genomes as the query se-quence folder.3.Press“add to data pool”,this should load several items into the pool list.4.Set the output folder as unzipped BRIGEXAMPLE2-ace folder.5.Make sure the BLAST options box is blank.。

222)(2 21Gaussian V V S m x eA New Approach of Image Denoising Based onDiscrete Wavelet TransformSami Hussien IsmaelDr. Firas Mahmood MustafaDr.İbrahim Taner OKÜMÜŞBioengineering and Sciences Department Technical College of Engineering (TCE)Bioengineering and Sciences Department Kahramanmaraş Sütçü İmam UniversityDuhok Polytechnic University (DPU)Kahramanmaraş Sütçü İmam UniversityKahramanmaraş, Turkey Duhok, IraqKahramanmaraş, Turkey Samihu54@Firas.mah.m@iokumus@.trAbstract —Image denoising is a process that used to enhance the image quality after degraded by the noise. There are several methods have been proposed for image denoising. In this paper, a new method of image denoising has been proposed. The proposed method is based on using wavelet transform.W avelet transform is best method for analysis the image due to the ability to split the image into sub-bands and work on each sub-band frequencies separately. Also, the robust median estimator has been used to estimate the noise ratio at the noisy image. According to experimental results, the proposed method presents best values for MSE and PSNR for denoised images. Also, by using different types of wavelet transform filters is make the proposed approach can obtained best results for image denoising process.Keywords: AGN; DWT; MSE; Noisy image; PSNR; Threshold;I.I NTRODUCTIONThe most images have non-stationary properties because their contents can be graduated from smooth areas to sharpen areas, where the smooth areas represent low frequencies regions while the sharpen area defines as a high frequencies regions [1]. These regions can be obtained by using two dimensional discrete wavelet transform DWT,where the approximation sub-band describes the low frequencies regions, and the three details sub-bands describes the high frequencies regions. For this reason the wavelet transform is appropriate to be used for study the properties of digital images [2].In [2], there are several approaches of image denoising have been proposed. DWT filters are the most popular one among them.Noise can be defined as any unwanted interference image data and noise often can be small values with high frequencies. Noise appears in images from multiple sources due to processed or procedure, transmissions reception. In addition, noise takes various forms such as uniform noise, noise impulse and also called the (Salt-and-Pepper) and Additive Gaussian Noise (AGN) that will be used during this research. The reason of choosing AGN at this work, because of this type of noise is include other types of noise implicitly. In addition, the possibility of appearing this type of noise in images is larger than other types of noise andnoisy image with AGN becomes more difficult during image denoising process. Fig. 1 shows the distribution of Gaussian noise and the AGN equation is:(1) Where:V :Standard-Deviation. m :Mean.Fig. 1 the distribution of Gaussian noiseII.P ROPOSED D ENOISING S CHEMEThe noisy image can be represented by using natural type of AGN and its equation:),(),(),(j i j i I j i In H (2) Where:I (i,j): Original image without noise.),(j i H :AGN.In (i,j): noisy image.The goal is to obtain the original image I (i, j) that contains Gaussian noise from the In (i, j) noisy image by applying a suitable method of image denoising [1],[3],[4], This means that: H (i,j) = 0.Wavelet transform is appropriate for the digital image denoising methods. Because it can be transforming the images into sub-bands, each one contains a certain frequencies that analyzed and processed easily [1],[5].Image denoising using DWT approach can be summarized in the following steps:2016 World Symposium on Computer Applications & Research),(j i xc 1.Apply one level 2-dim DWT on noisy image (the noisy image divided into four sub-bands (Low-low LL, Low-high LH, High-low HL and High-high HH sub-bands). 2.Find the threshold value for each sub-band (LH, HL and HH).pare the threshold value of each sub-band with all pixel values of selected sub-band. If the pixel value less than threshold value, then set the pixel value to be zero. Otherwise, leave it and select the next pixel value. This step repeated until the last pixel value of selected sub-band.4.Apply one level inverse 2-dim DWT on the sub-bands to obtain a new image without noise.5.Find the values of mean square error (M SE) and peak signal-to-noise ratio (PSNR) for new image and original image to evaluate the proposed image denoising method. To compute the values of MSE and PSNR, the following equation is used:>@2101),(),(.1¦¦ M i N j j i I j i F N M MSE (3)MSEPSNR 2)255(log.10 (4)Where:I (i, j): Original image. F (i, j): New image M and N: size of image255: Max pixel value of grayscale image.The selection of the threshold value is important factor in decision making to delete or keep the pixel values of selected image sub-band [6]. Therefore, the threshold value must be high for denoising purpose and small value to maintain properties of the image. The threshold value can be found by applying the following equation [1].x Thx V V 2(5)Where:Thx : Threshold value.2V :Noise value of noisy image.x V :Standard deviation for one of these sub-bands (LH,HL and HH), and can be calculated by equation:NN i m i x ¦102)(V(6)The standard deviation value for each sub-band gives a uniform threshold value for its properties. TheVThthreshold value has an inverse relationship with thestandard deviation of the sub-band and it has positiverelationship with the standard deviation value of the noisyimage. In case (1 xV V) that means the pixel values of sub-band greater than the noise value. Therefore, the VThvalue must be select with minimum value to maintain the several properties of the pixel values of sub-band and denoise some pixel values of sub-band. While, in case (1!!xV V ) that means the pixel values of sub-band has a high value of noise. Therefore, the VTh must be select withmaximum value to denoise a several pixel values of sub-band and this can be lead to loss many properties of the pixel values of sub-band [1] .The noise power (2V ) can be computed by the estimation method that called (Robust Median Estimator) and applying the following formula [1].6745.0/),(j i x MedianV (7)Where x (i, j): represent analysis of diagonal sub-band for the first stage (HH or HL).In this paper, a new algorithm of image denoising has been proposed based on using DWT with two-stage of analysis. During the algorithm implementation, two grayscale images with sizes (256 × 256) that shown in Fig. 2 and noise type is additive Gaussian noise with zero rate (m = 0) and the standard deviation values (V =10, V =15, V =25). The four (LL, LH, HL and HH) sub-bands of the selected noisy image can be obtained by applying the 2-dim DWT.(a) Camera man (b) LenaFig. 2 the original imagesThe block diagram that shown in Fig. 3 is describe the image denoising process of the proposed method.The image denoising method not has any information about the amount of additive noise in contents of the noisy image. For this reason, the estimation method is used to estimate the amount of noise by using Robust M edian Estimator [1].After computing the noise value, 2-dim DWT with two stages is applied on the noisy image to obtain the (LH, HL, HH, LH1, HL1 and HH1) sub-bands. Then, the standard deviation for each sub-band is computed to use it in the equation (5) to calculate the threshold value for each sub-band and equation (8) is used for comparison process.°¿°¾½°¯°®­t c otherwise Thx x j i x j i x ,0),,(),( (8)Where,),(j i x : The pixel values of noisy image sub-band. :The pixel value of denoised image.Finally, 2-dim inverse DWT with two stages is applied on these sub-bands to obtain denoised image.According to analysis of these sub-bands, the image denoising algorithm works on the following states:State 1: Apply one level 2-dim DWT on noisy image and compute Thx for these (LH, HL and HH) sub-bands. Then, the equation (8) is applied on all pixelvalues of these sub-bands. An inverse 2-dim DWTis applied on all sub-bands to construct a denoisedimage. Calculate M SE and PSNR between thedenoised image and original image.State 2: Obtain a (LL) sub-band by applying one level 2-dim DWT on the noisy image. And then apply 2-dim DWT on (LL) sub-band to obtain (LH1, HL1and HH1) sub-bands and calculate Thx for thesesub-bands. Then, equation (8) is applied on allpixel values of these sub-bands. To obtain thedenoised image an inverse 2-dim DWT is appliedon all pute M SE and PSNRbetween the denoised image and the original image. State 3: Apply one level 2-dim DWT on noisy image to obtain these (LH and HL) sub-bands, find their thxvalue by applying threshold method and set thepixel values of HH sub-band to be all zero values.Equation (8) is applied on (LH and HL) sub-bands.Then, apply an inverse 2-dim DWT for all sub-bands to construct a denoised image. CalculateM SE and PSNR between the denoised image andoriginal image.State 4: Obtain (LH)sub-band by applying one level 2-dim DWT on the noisy image, find its thx value byapplying threshold method and set the pixel valuesof (HL and HH) sub-bands to be all zero values.Equation (8) is applied on (LH) sub-band. Then, adenoised image can be obtained by applying aninverse 2-dim DWT on all sub-bands. Find M SEand PSNR values for the denoised image andoriginal image.State 5: Divide the noisy image into (LL, HL, LH and HH) sub-bands by applying one level 2-dim DWT.Then, compute thx value for (HL)sub-bands andset the pixel values of (LH and HH) sub-bands tobe all zero values. Equation (8) is applied on (HL)sub-band. Then, apply an inverse 2-dim DWT onall sub-bands to construct a denoised image.Compare between the denoised image and originalimage according to their MSE and PSNR values. State 6: One level 2-dim DWT is applied on noisy image to obtain (LL, HL, LH and HH) sub-bands. And then,set (HL, LH and HH) sub-bands to be all zerovalues.An inverse 2-dim DWT is applied on allsub-bands to construct a denoised image. CalculateM SE and PSNR between the denoised image andoriginal image.Fig. 3 the proposed method block diagramIII.E XPERIMENTAL R ESULTSM atlab technical programming language has been used to implement the proposed method. AGN is added to testoriginal image and the quantity of this noise must be notmore than a half amount of the standard deviation of theseoriginal images. Otherwise, if the noise amount is great thatmeans the denoising process will be remove more pixel values of the original image.The implementation results of proposed algorithm onCamera man image shows in Fig. 4 with the standard deviation is the (62.341). After AGN with values (V=10, V=15 and V=25) is added to it, the value of standard deviation has been became (62.928,63.459 and 65.211).Then, 2-dim DWT with one stage is applied on noisy imageto obtain high frequency sub-bands (HH, HL and LH). Toestimate the value of noise, equation (7) has been applied on (HH) sub-band and the estimation values of additive Gaussian noise for Camera man and Lena images tabulated in Table (1). By applying the equation (6) to obtain the threshold value Thx for each sub-band.Table 1: Standard deviation Std values for Camera man and Lenaimages using HH sub-bandImageStdoriginalimageStdNoise=10StdNoise=15StdNoise=25Stdestimation noise=10Stdestimation noise=15Stdestimation noise=25Cameraman62.34162.92863.45965.21111.02515.56624.723Lena52.29153.12454.19957.07010.71715.59024.416 According to experimental results for Camera man image that shown in Table (2), the proposed method at state (one sub-band deletion (HH) sub-band) has been achieved best results at noise ratio (V=10) and type of DWT filter is Rbior. While, in the state (all sub-band deletion), the proposed method has been achieved best results at the noise ratio (V=15 and V=25) and type of DWT filter is Sym.Fig. 4 Camera man image (a) Image with noise 10 (b)Denoised image without deleting level one (c)Denoised image without deleting level two (d)Denoised Image with HH sub-band deletion (e) Denoised image with HH and HL sub-bands deletion (f) Denoised image with HH, HL and LH sub-band deletion.Also, the proposed method is presented best values of PSNR for Camera man image with V =10 in state HH sub-band deletion among other states as shown in Fig. 5. While, in state all sub-bands deletion with V =15 and V =25, the proposed method presents best PSNR values for Camera man image as shown in Fig. 6 and Fig. 7.Fig .5 PSNR values for camera man image at V =10Table 3. shows the comparison of PSNR and M SEvalues for camera man image at two levels of DWT with V=10 between the proposed method and methods thatproposed in [7]. According to results, the proposed method is presented best PSNR and MSE values than methods thatproposed in [7].Table 2:MSE and PSNR values for Camera man image at different waveletfiltersImage Denoising MethodsOne analysis level Two analysis levelDelete HHDelete HH and HLDelete HH, HL and LH Filter NameMSE 88.24287.86281.71299.308104.782CoifPSNR 28.67428.69329.00828.16127.928MSE74.32374.32275.98594.347101.248BiorPSNR 29.42029.42029.32428.38428.077MSE 74.93174.76068.23294.37498.715RbioPSNR 29.38429.39429.79128.38228.187MSE 88.08287.88780.37389.94098.189dbPSNR 28.68228.69229.08028.59128.210MSE 87.49387.14480.42289.94096.324SymPSNR 28.71128.72829.07728.59128.293MSE 135.265140.929105.967118.99389.694HaarPSNR 26.81926.64127.87927.37628.603MSE167.161173.368104.085151.99788.546DmeyPSNR25.89925.74127.95726.31228.659Table 3. Comparison of PSNR and MSE values for Camera man image attwo levels of DWT with V =10.Also, Fig. 8 shows Lena image after the proposedmethod has been applied on it. Depending on the experimental results that shown in table 4,the proposed method at state (two sub-bands deletion (HH and LH) sub-bands has been achieved best results at noise ratio (V =10) and type of DWT filter is Bior 5.5 , While, in the state (all sub-band deletion), the proposed method has been achieved best results at the noise ratio (V =15) and type of DWT filter is Sym4, While, in the state (all sub-band deletion), the proposed method has been achieved best results at the noise ratio (V =25) and type of DWT filter is Sym5.Fig. 8 Lena image (a) Image with noise 10 (b) Denoised image without deleting level one (c) Denoised image without deleting level two (d)DWT LevelUniversal Threshold Visu Shrink Proposed Method MSEPSNRMSEPSNRMSEPSNR1st Level 564.92720.610548.29720.74074.32329.4202nd Level813.40319.027742.40319.42474.32229.420(a) (b) (c)(d) (e) (f)(a) (b) (c)(d) (e) (f)Denoised Image with HH sub-band deletion (e) Denoised image with HH and LH sub-bands deletion (f) Denoised image with HH, HL and LH sub-band deletion.In addition, the proposed algorithm is achieved best values of PSNR for Lena image with V =10 in state HH and LH sub-band deletion among other states as shown in Fig. 9. While, in state all sub-bands deletion with V =15 and V =25, the proposed method presents best PSNR values for Camera man image as shown in Fig. 10 and Fig. 11.Fig .9 PSNR values for Lena image at V =10Fig .10 PSNR values for Lena image at V =15Fig .11 PSNR values for Lena image at V =25IV.C ONCLUSIONIn this research, a new method of image denoising hasbeen proposed. The proposed method based on DWT that represents a best method for analysis the image due to the ability to split the image into sub-bands and work on each sub-band frequency separately. Also, the robust median estimator has been used to estimate the noise ratio in the noisy image. According to experimental results, the proposed method presents best values of MSE and PSNR for denoised images.Also, by using different types of wavelet transform filters is make the proposed approach can obtained best results for image denoising process.In future, the proposed method can be modified by more accurate estimation function to enhance its ability at image denoising process.Table 4: MSE and PSNR values for Lena image at different wavelet filtersImage Denoising MethodsOne analysis levelTwo analysis levelDelete HHDelete HH and LHDelete HH, HL and LHFilter NameMSE 94.26093.95482.27070.90971.284CoifPSNR 28.38828.40228.97829.62429.601MSE 82.60782.60472.92366.05069.927BiorPSNR 28.96128.96129.50229.93229.684MSE 82.09982.39767.25266.35571.962RbioPSNR28.98728.97229.85429.91229.560MSE 93.94693.77480.89468.56669.473dbPSNR 28.40228.41029.05229.77029.713MSE 93.89693.72280.89468.56669.712SymPSNR28.40428.41229.05229.77029.698MSE 94.450106.30977.64784.97096.829HaarPSNR28.37927.86529.23028.83828.271MSE 81.00692.72174.01582.61894.359DmeyPSNR29.04628.45929.43828.96028.383R EFERENCES[1]S. G. Chang, B. Yu, and M. Vetterli, “Adaptive Wavelet Thresholding for Image Denoising and Compression”, IEEE Transactions on Image Processing, vol. 9, no. 9, September 2000.[2]R. K. Rai, J. Asnani and T. R. Sontakke, “Review of Shrinkage Techniques for Image Denoising”, International Journal of Computer Applications (0975 – 8887), vol. 42, no.19, March 2012, pp. 13-16[3]P. Moulin, “Multiscale Image Decompositions and Wavelets”,Handbook of Image and Video Processing, 2nd edition, Academic Press, 2005[4] C.S. Burrus, R.A. Gopinath and H. GUO , “Introduction to Wavelets and Wavelet Transforms: A Primer ”. Prentice Hall, 1998.[5]A. Hamza and H. Krim, “Image Denoising: A Nonlinear Rob ust Statistical Approach”, IEEE Transactions on Signal Proce ssing, vol. 49, no. 12, pp. 3045-3054, December 2001.[6]A. Al Jumah, “Denoising of an Image Using Discrete Stationary Wavelet Transform and Various Thresholding Techniques”, Journal of Signal and Information Processing, vol. 4, pp.33-41, February 2013.[7]Anuta m and Rajni, “Performance Analysis of Image Denoising with Wavelet Thresholding M ethods For Different Levels of Decomposition”, The International Journal of Multimedia & Its Applications (IJMA) vol.6, no.3, pp.35-46, June 2014.P S NR。