именно с отчества и нужно начинать - если кончается на "А" - значит женщина, иначе мужчина (русский,украинский и белорусский точно) и исходя из этого уже склонять фамилию.