DOC PREVIEW
Engineering a Scalable Placement Heuristic for DNA Probe Arrays

This preview shows page 1-2-3-21-22-23-43-44-45 out of 45 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Engineering a Scalable Placement Heuristic for DNA Probe ArraysOutlineSlide 3DNA Probe ArraysSimplified DNA Array FlowArray Manufacturing ProcessPowerPoint PresentationProbe SynthesisMeasuring Unwanted IlluminationSynchronous vs. Asynchronous SynthesisSlide 11Problem Formulation (Synchronous Case)2-D Placement Lower BoundTSP+1-Threading PlacementSlide 15Slide 16Slide 17Slide 18Epitaxial Placement AlgorithmTile- and Row- EpitaxialSlide 21Slide 22Slide 23Problem Formulation (Asynchronous Case)Lower BoundSlide 263-D Placement FlowsAlgorithms for In-Place Probe AlignmentSlide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Enhanced DNA Array Design FlowSlide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Engineering a Scalable Placement Heuristic for DNA Probe ArraysA.B. Kahng, I.I. Mandoiu, P. Pevzner, A.B. Kahng, I.I. Mandoiu, P. Pevzner, S. Reda (all UCSD), A. Zelikovsky (GSU)S. Reda (all UCSD), A. Zelikovsky (GSU)Outline•DNA probe arrays and unwanted illumination•Synchronous array design (2-D placement)•Asynchronous array design (3-D placement)•Experimental results•Extensions•ConclusionsOutline•DNA probe arrays and unwanted illumination•Synchronous array design (2-D placement)•Asynchronous array design (3-D placement)•Experimental results•Extensions•ConclusionsDNA Probe Arrays•Used in wide range of genomic analyses–Gene expression monitoring, SNP mapping, sequencing by hybridization,…•Arrays with up to 1000x1000 probes in commercial use, 108 probes envisioned for next generation arrays–Highly scalable algorithms required for array designSimplified DNA Array FlowProbe SelectionArray ManufacturingHybridization ExperimentGene sequences, position of SNPs, etc.Analysis of Hybridization IntensitiesMask ManufacturingSoft/Computational DomainHard/Biochemistry Domain Mask Design: Placement & EmbeddingArray Manufacturing ProcessVery Large-Scale Immobilized Polymer Synthesis:1. Treat substrate with chemically protected “linker” molecules, creating rectangular array–Site size = approx. 10x10 microns2. Selectively expose array sites to light–Light deprotects exposed molecules, activating further synthesis3. Flush chip surface with solution of protected A,C,G,T–Binding occurs at previously deprotected sites4. Repeat steps 2&3 until desired probes are synthesizedPhoto-Deprotection Step Our concern: diffraction unwanted illumination yield decreaseProbe SynthesisNucleotide deposition sequence ACGG  M3C  M2A  M1 CG AC CG AC ACG AG G AG C Placed probesAAAA AC CC C CCG G GG GGMeasuring Unwanted IlluminationNucleotide deposition sequence ACGG  M3C  M2A  M1AAAA AC CC C CCG G GG GG borderUnwanted illumination  border length CG AC CG AC ACG AG G AG C Placed probesSynchronous vs. Asynchronous Synthesis(a) periodic deposition sequence(b) Synchronous embedding of CTG(c) Asynchronous leftmost embedding of CTG(d) Another asynchronous embeddingTGCATGTGCA…CA4-group(a)CGT(b)CTG(c)GCT(d)Outline•DNA probe arrays and unwanted illumination•Synchronous array design (2-D placement)•Asynchronous array design (3-D placement)•Experimental results•Extensions•ConclusionsProblem Formulation (Synchronous Case)Synchronous Array Design (2-D Placement) Problem:•Minimize placement cost of Hamming graph H (vertices = probes, distance = Hamming)•On 2-dimensional grid graph G2 (N x N array, edges b/w distance 1 neighbors)HprobeG2site2-D Placement Lower Bound•Sum of Hamming distances to 4 closest neighbors minus weight of 4N heaviest arcsHprobeG2TSP+1-Threading PlacementHubbell 90’s•Find TSP tour/path over given probes w.r.t. Hamming distance •Thread TSP path in the grid row by rowHannenhalli,Hubbell,Lipshutz, Pevzner’02•Place the probes according to 1-Threading •Further decreases total border by 20%Lexicographical Sorting +1-ThreadingAATGCAATGATGGRadix-sort the probes in lexicographical order1 2 3CCThread on the chipMatching Based Probe Placement13254Select an independent (mutually nonadjacent) set of placed probesRe-embed using optimal perfect matching22314Total cost can only decrease or remain the sameRuntime: roughly proportional to square of independent set sizeSliding Window MatchingThere is a trade-off between solution quality and size/overlap of windowsIterate SlidingWindowMatching over the chip until improvement drops below 0.1%Effect of Window Size on Solution QualityIncreased window size/overlap decreases number of conflicts, but increases runtimeEpitaxial Placement Algorithm• Simulates crystal-growth• Start with arbitrary probe placed at center• Maintain a best probe-candidate (i.e, a probe with min number of conflicts to the already placed neighbors) for each border site• Iteratively fill the border site with minimum increase in border length- give priority to sites with more neighbors filledTile- and Row- Epitaxial•Tile-epitaxial–Divide array into 100x100 tiles–Run Epitaxial within each tile–Take into account border of already placed tiles•Row-epitaxial–Place probes by a fast method, e.g., sort+1-thread–Re-place probes row by row, sequentially filling sites within a row–Assign to each site a probe with min number of conflicts among the unplaced probes from following K rows2-D Placement Algorithm Comparison: Border Conflict02000000400000060000008000000100000001200000014000000100 200 300 500LBRow-EPTXEPTXTile-EPTXTSP+1ThrSWM 6x62-D Placement Algorithm Comparison: Runtime1101001000100001000001000000100 200 300 500 1000TSP+1ThrRow-EPTXEPTXTile-EPTXSWMOutline•DNA probe arrays and unwanted illumination•Synchronous array design (2-D placement)•Asynchronous array design (3-D placement)•Experimental results•Extensions•ConclusionsProblem Formulation (Asynchronous Case)•Asynchronous synthesis:–Periodic nucleotide deposition sequence, e.g., (ACTG)p–Every probe grows asynchronously  Border length = Hamming distance between embedded probes •Asynchronous Array (3-D Placement) Design Problem: –Minimize placement cost of embedded-probe Hamming graph H (vertices=probes, distance = Hamming b/w embedded probes)–on 2-dimensional grid graph G2 (N x N array, edges b/w neighbors)HprobeG2siteLower Bound•Sum of distances to 4 closest neighbors minus weight of 4N heaviest


Engineering a Scalable Placement Heuristic for DNA Probe Arrays

Download Engineering a Scalable Placement Heuristic for DNA Probe Arrays
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Engineering a Scalable Placement Heuristic for DNA Probe Arrays and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Engineering a Scalable Placement Heuristic for DNA Probe Arrays 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?