Search Results - (Author, Cooperation:D. Z. Chen)
-
1Latest Papers from Table of Contents or Articles in PressM. B. Gerstein ; A. Kundaje ; M. Hariharan ; S. G. Landt ; K. K. Yan ; C. Cheng ; X. J. Mu ; E. Khurana ; J. Rozowsky ; R. Alexander ; R. Min ; P. Alves ; A. Abyzov ; N. Addleman ; N. Bhardwaj ; A. P. Boyle ; P. Cayting ; A. Charos ; D. Z. Chen ; Y. Cheng ; D. Clarke ; C. Eastman ; G. Euskirchen ; S. Frietze ; Y. Fu ; J. Gertz ; F. Grubert ; A. Harmanci ; P. Jain ; M. Kasowski ; P. Lacroute ; J. Leng ; J. Lian ; H. Monahan ; H. O'Geen ; Z. Ouyang ; E. C. Partridge ; D. Patacsil ; F. Pauli ; D. Raha ; L. Ramirez ; T. E. Reddy ; B. Reed ; M. Shi ; T. Slifer ; J. Wang ; L. Wu ; X. Yang ; K. Y. Yip ; G. Zilberman-Schapira ; S. Batzoglou ; A. Sidow ; P. J. Farnham ; R. M. Myers ; S. M. Weissman ; M. Snyder
Nature Publishing Group (NPG)
Published 2012Staff ViewPublication Date: 2012-09-08Publisher: Nature Publishing Group (NPG)Print ISSN: 0028-0836Electronic ISSN: 1476-4687Topics: BiologyChemistry and PharmacologyMedicineNatural Sciences in GeneralPhysicsKeywords: Alleles ; Cell Line ; DNA/*genetics ; *Encyclopedias as Topic ; GATA1 Transcription Factor/metabolism ; Gene Expression Profiling ; Gene Regulatory Networks/*genetics ; Genome, Human/*genetics ; Genomics ; Humans ; K562 Cells ; *Molecular Sequence Annotation ; Organ Specificity ; Phosphorylation/genetics ; Polymorphism, Single Nucleotide/genetics ; Protein Interaction Maps ; RNA, Untranslated/genetics/metabolism ; Regulatory Sequences, Nucleic Acid/*genetics ; Selection, Genetic/genetics ; Transcription Factors/*metabolism ; Transcription Initiation SitePublished by: -
2Latest Papers from Table of Contents or Articles in PressD. Z. Chen ; C. Y. Shi ; Q. An ; Q. Zeng ; W. L. Mao ; W. A. Goddard, 3rd ; J. R. Greer
American Association for the Advancement of Science (AAAS)
Published 2015Staff ViewPublication Date: 2015-09-19Publisher: American Association for the Advancement of Science (AAAS)Print ISSN: 0036-8075Electronic ISSN: 1095-9203Topics: BiologyChemistry and PharmacologyComputer ScienceMedicineNatural Sciences in GeneralPhysicsPublished by: -
3Articles: DFG German National LicensesStaff View
ISSN: 1432-0541Keywords: Shortest paths ; Interval graphs ; Circular-arc graphs ; Union-find algorithms ; Minimum circle coverSource: Springer Online Journal Archives 1860-2000Topics: Computer ScienceMathematicsNotes: Abstract We give the first linear-time algorithm for computing single-source shortest paths in a weighted interval or circular-arc graph, when we are given the model of that graph, i.e., the actual weighted intervals or circular-arcsand the sorted list of the interval endpoints. Our algorithm solves this problem optimally inO(n) time, wheren is the number of intervals or circular-arcs in a graph. An immediate consequence of our result is anO(qn + n logn)-time algorithm for the minimum-weight circle-cover problem, whereq is the minimum number of arcs crossing any point on the circle; then logn term in this time complexity is from a preprocessing sorting step when the sorted list of endpoints is not given as part of the input. The previously best time bounds were0(n logn) for this shortest paths problem, andO(qn logn) for the minimum-weight circle-cover problem. Thus we improve the bounds of both problems. More importantly, the techniques we give hold the promise of achieving similar (logn)-factor improvements in other problems on such graphs.Type of Medium: Electronic ResourceURL: -
4Articles: DFG German National LicensesStaff View
ISSN: 1432-0541Keywords: Key words. Algorithms, EREW PRAM, Merging, Multiselection, Partitioning, Sorting, Parallel computing.Source: Springer Online Journal Archives 1860-2000Topics: Computer ScienceMathematicsNotes: Abstract. We consider the following partition problem: Given a set S of n elements that is organized as k sorted subsets of size n/k each and given a parameter h with 1/k ≤ h ≤ n/k , partition S into g = O(n/(hk)) subsets D 1 , D 2 , . . . , D g of size Θ(hk) each, such that, for any two indices i and j with 1 ≤ i 〈 j ≤ g , no element in D i is bigger than any element in D j . Note that with various combinations of the values of parameters h and k , several fundamental problems, such as merging, sorting, and finding an approximate median, can be formulated as or be reduced to this partition problem. The partition problem also finds many applications in solving problems of parallel computing and computational geometry. In this paper we present efficient parallel algorithms for solving the partition problem and a number of its applications. Our parallel partition algorithm runs in O( log n) time using $$ O\left(\frac{\min\{(n/h)*\max\{\log h,1\}, n*\max\{\log(1/h),1\}\}}{\log n}\right) $$ processors in the EREW PRAM model. The complexity bounds of our parallel partition algorithm on the respective special cases match those of the optimal EREW PRAM algorithms for merging, sorting, and finding an approximate median. Using our parallel partition algorithm, we are also able to obtain better complexity bounds (even possibly on a weaker parallel model) than the previously best known parallel algorithms for several important problems, including parallel multiselection, parallel multiranking, and parallel sorting of k sorted subsets.Type of Medium: Electronic ResourceURL: -
5Articles: DFG German National LicensesStaff View
ISSN: 1432-0541Keywords: Key words. Parallel algorithms, Maximum matching problems, Interval graphs, Complement graphs, EREW PRAM, Hypercubes.Source: Springer Online Journal Archives 1860-2000Topics: Computer ScienceMathematicsNotes: Abstract. Given a set of n intervals representing an interval graph, the problem of finding a maximum matching between pairs of disjoint (nonintersecting) intervals has been considered in the sequential model. In this paper we present parallel algorithms for computing maximum cardinality matchings among pairs of disjoint intervals in interval graphs in the EREW PRAM and hypercube models. For the general case of the problem, our algorithms compute a maximum matching in O( log 3 n) time using O(n/ log 2 n) processors on the EREW PRAM and using n processors on the hypercubes. For the case of proper interval graphs, our algorithm runs in O( log n ) time using O(n) processors if the input intervals are not given already sorted and using O(n/ log n ) processors otherwise, on the EREW PRAM. On n -processor hypercubes, our algorithm for the proper interval case takes O( log n log log n ) time for unsorted input and O( log n ) time for sorted input. Our parallel results also lead to optimal sequential algorithms for computing maximum matchings among disjoint intervals. In addition, we present an improved parallel algorithm for maximum matching between overlapping intervals in proper interval graphs.Type of Medium: Electronic ResourceURL: