People from the DNATree claim that they are able to proof that someone actually possess the Cohen genes. According to the Halachic Law, it is needed to have witnesses to testify both the ancestry and the type of it, so, when somebody searches for his/her origins (while assuming they have a Jewish Soul), is the DNA Testing, a document that can help the person go through the whole process?

I am uncertain whether the DNA testing has Halachic validity. Even assuming it is valid, all it would prove is whether someone has a male antecedent who was a Cohen. At some point, an ancestor may have married a woman who is Non-Jewish, divorced, or invalid for a Cohen for other reasons, and these would invalidate the individual from being a Cohen.