Yinglei Song
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Yinglei Song has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Chunmei Liu
Department of Systems and Computer Science, Howard University, Washington, DC 20059, USA
3 shared publications - Chunmei Liu
Department of Computer Science, University of Georgia, Athens, GA 30602, USA
1 shared publication - Legand Burge
Howard University
1 shared publication - Liming Cai1 shared publication
Ping Hu
1 shared publication- Russell L. Malmberg
Department of Plant Biology, University of Georgia, Athens, GA 30602, USA
1 shared publication
Latest Publications
- 15 April 2010
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 22 (4) , 684-698
Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
In this paper, we study the parameterized complexity of Dominating Set problem in chordal graphs and near chordal graphs. We show the problem is W[2]-hard and cannot be solved in time n o(k) in chordal and s-chordal (s>3) graphs unless W[1]=FPT. In addition, we obtain inapproximability results for computing a minimum dominating set in chordal and near chordal graphs. Our results prove that unless NP=P, the minimum dominating set in a chordal or s-chordal (s>3) graph cannot be approximated within a ratio of \(\frac{c}{3}\ln{n}\) in polynomial time, where n is the number of vertices in the graph and 0<c<1 is the constant from the inapproximability of the minimum dominating set in general graphs. In other words, our results suggest that restricting to chordal or s-chordal graphs can improve the approximation ratio by no more than a factor of 3. We then extend our techniques to find similar results for the Independent Dominating Set problem and the Connected Dominating Set problem in chordal or near chordal graphs.- 15 April 2010
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 22 (4) , 684-698
Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
In this paper, we study the parameterized complexity of Dominating Set problem in chordal graphs and near chordal graphs. We show the problem is W[2]-hard and cannot be solved in time n o(k) in chordal and s-chordal (s>3) graphs unless W[1]=FPT. In addition, we obtain inapproximability results for computing a minimum dominating set in chordal and near chordal graphs. Our results prove that unless NP=P, the minimum dominating set in a chordal or s-chordal (s>3) graph cannot be approximated within a ratio of \(\frac{c}{3}\ln{n}\) in polynomial time, where n is the number of vertices in the graph and 0<c<1 is the constant from the inapproximability of the minimum dominating set in general graphs. In other words, our results suggest that restricting to chordal or s-chordal graphs can improve the approximation ratio by no more than a factor of 3. We then extend our techniques to find similar results for the Independent Dominating Set problem and the Connected Dominating Set problem in chordal or near chordal graphs.- 13 February 2008
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 18 (1) , 87-97
Parameterized dominating set problem in chordal graphs: complexity and lower bound
- 13 February 2008
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 18 (1) , 87-97
Parameterized dominating set problem in chordal graphs: complexity and lower bound
- 3 August 2007
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 16 (1) , 39-49
Parameterized lower bound and inapproximability of polylogarithmic string barcoding
- 3 August 2007
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 16 (1) , 39-49
Parameterized lower bound and inapproximability of polylogarithmic string barcoding
- 1 January 2006
- p. 99-110
Efficient annotation of non-coding RNA structures including pseudoknots via automated filters.
Computational search of genomes for RNA secondary structure is an important approach to the annotation of non-coding RNAs. The bottleneck of the search is sequence-structure alignment, which is often computationally intensive. A plausible solution is to devise effective filters that can efficiently remove segments unlikely to contain the desired structure patterns in the genome and to apply search only on the remaining portions. Since filters can be substructures of the RNA to be searched, the strategy to select which substructures to use as filters is critical to the overall search speed up. Such an issue becomes more involved when the structure contains pseudoknots; approaches that can filter pseudoknots are yet available. In this paper, a new effective filtration scheme is introduced to filter RNA pseudoknots. Based upon the authors' earlier work in tree-decomposable graph model for RNA pseudoknots, the new scheme can automatically derive a set of filters with the overall optimal filtration ratio. Search experiments on both synthetic and biological genomes showed that, with this filtration approach, RNA structure search can speed up 11 to 60 folds while maintaining the same search sensitivity and specificity of without the filtration. In some cases, the filtration even improves the specificity that is already high.
- 1 January 2006
- p. 99-110
Efficient annotation of non-coding RNA structures including pseudoknots via automated filters.
Computational search of genomes for RNA secondary structure is an important approach to the annotation of non-coding RNAs. The bottleneck of the search is sequence-structure alignment, which is often computationally intensive. A plausible solution is to devise effective filters that can efficiently remove segments unlikely to contain the desired structure patterns in the genome and to apply search only on the remaining portions. Since filters can be substructures of the RNA to be searched, the strategy to select which substructures to use as filters is critical to the overall search speed up. Such an issue becomes more involved when the structure contains pseudoknots; approaches that can filter pseudoknots are yet available. In this paper, a new effective filtration scheme is introduced to filter RNA pseudoknots. Based upon the authors' earlier work in tree-decomposable graph model for RNA pseudoknots, the new scheme can automatically derive a set of filters with the overall optimal filtration ratio. Search experiments on both synthetic and biological genomes showed that, with this filtration approach, RNA structure search can speed up 11 to 60 folds while maintaining the same search sensitivity and specificity of without the filtration. In some cases, the filtration even improves the specificity that is already high.